AtCoder Weekday Contest 001
AtCoder Weekday Contest 001 풀이
2026년 7월 30일 · 3 min read
AtCoder Weekday Contest 001 풀이
답은 이 자명하다.
print(int(input()) + 1)구간 사이에 있는 얘들만 넣고 정렬
int n,l,r;
void solve(){
ri(n, l, r);
vp v;
for(int i = 0; i < n; i++){
int x; ri(x);
if(l <= x and x <= r) v.pb({x, i + 1});
}
if(v.empty()){
po(-1);
return;
}
sort(all(v), [&](auto& a, auto& b){
return a.fi == b.fi ? a.se < b.se : a.fi > b.fi;
});
po(v[0].se);
}내림차순 정렬 이후 개만 보기
int n,k,res;
void solve(){
ri(n, k);
vi v(n); ri(v); sort(rall(v));
for(int i = k; i < n; i++) res += v[i];
po(res);
}: 번째 원소를 반드시 선택했고, 총 비용이 일 때 만들 수 있는 최대 가치
int n,m,k,A[222], B[222];
auto solve = [](){
ri(n, m, k);
for(int i = 1; i <= n; i++) ri(A[i], B[i]);
vector<vector<int>> dp(n + 1, vi(m + 1, -inf));
int res = -inf;
for(int i = 1; i <= n; i++){
dp[i][B[i]] = max<int>(dp[i][B[i]], A[i]);
for(int j = max<int>(1, i - k); j < i; j++){
for(int c = 0; c + B[i] <= m; c++){
if(dp[j][c] == -inf) continue;
dp[i][c + B[i]] = max<int>(dp[i][c + B[i]], dp[j][c] + A[i]);
}
}
for(int c = 0; c <= m; c++) res = max<int>(res, dp[i][c]);
}
po(res);
};구간 최대, 구간 최소를 지원하는 세그를 짜면 에 해결 가능
struct mxsegtree{
const int sz = 1 << 18;
vector<int> tree;
mxsegtree():tree(sz << 1, -inf){}
void U(int i, int val){
--i |= sz; tree[i] = val;
while(i >>= 1) tree[i] = max<int>(tree[i << 1], tree[i << 1 | 1]);
}
int Q(int l, int r){
int res = -inf;
--l |= sz; --r |= sz;
while(l <= r){
if(l & 1) res = max<int>(res, tree[l++]);
if(~r & 1) res = max<int>(res, tree[r--]);
l >>= 1, r >>= 1;
}
return res;
}
} mxseg;
struct mnsegtree{
const int sz = 1 << 18;
vector<int> tree;
mnsegtree():tree(sz << 1, inf){}
void U(int i, int val){
--i |= sz; tree[i] = val;
while(i >>= 1) tree[i] = min<int>(tree[i << 1], tree[i << 1 | 1]);
}
int Q(int l, int r){
int res = inf;
--l |= sz; --r |= sz;
while(l <= r){
if(l & 1) res = min<int>(res, tree[l++]);
if(~r & 1) res = min<int>(res, tree[r--]);
l >>= 1, r >>= 1;
}
return res;
}
} mnseg;
int n,k;
auto solve = [](){
ri(n, k);
for(int i = 1; i <= n; i++){
int x; ri(x);
mxseg.U(i, x); mnseg.U(i, x);
}
int mx = -inf;
for(int i = 1; i + k - 1 <= n; i++){
int l = i, r = i + k - 1;
mx = max<int>(mx, mxseg.Q(l, r) - mnseg.Q(l, r));
}
po(mx);
};