| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1038462 | Marco_Escandon | 송신탑 (IOI22_towers) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#include "fish.h"
typedef long long ll;
#define x first
#define y second
long long max_weights(int n, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> w) {
vector<vector<pair<ll,ll>>> cad(n+1);
vector<vector<ll>> sol(n+1),sol2(n+1);
for(int i=0; i<X.size(); i++)
cad[X[i]+1].push_back({Y[i]+1,w[i]});
for(int i=0; i<cad.size(); i++)
{
cad[i].push_back({0,0});
sort(cad[i].begin(),cad[i].end());
cad[i].push_back({1e9,0});
for(int j=1; j<cad[i].size(); j++)
cad[i][j].y+=cad[i][j-1].y;
sol[i].resize(cad[i].size());
sol2[i].resize(cad[i].size());
}
sol[0][0]=0;
sol[0][1]=0;
sol2[0][0]=0;
sol2[0][1]=0;
for(int i=1; i<sol.size(); i++)
{
ll p=0;
for(int j=0; j<sol[i].size(); j++)
{
while(p<cad[i-1].size()&&cad[i-1][p]<=cad[i][j]) p++;
p--;
sol[i][j]=max(sol[i][j],sol2[i-1][p]+cad[i-1][p].y);
if(i>=3)
sol[i][j]=max(sol[i][j],sol[i-2].back()+cad[i-1].back().y);
}
for(int j=0; j<sol[i].size(); j++)
{
sol2[i][j]=sol[i][j]-cad[i][j].y;
if(j>=1)
{
sol2[i][j]=max(sol2[i][j],sol2[i][j-1]);
sol[i][j]=max(sol[i][j],sol[i][j-1]);
}
}
}
return sol.back().back();
}