이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=1505;
ll dp[MX][MX], par[MX][MX];
int cur[MX], fr[MX], bk[MX];
int N,M;
vector<int> work(vector<pair<int,int>> v) {
for(int i=0;i<=N;i++) {
for(int j=0;j<=N;j++) {
dp[i][j]=-1e18;
par[i][j]=0;
}
}
dp[0][N/2]=0;
for(int i=0;i<N;i++) {
for(int j=0;j<=N;j++) {
if(dp[i][j]==-1e18) continue;
if(j+1<=N && dp[i][j]+v[i].second>dp[i+1][j+1]) {
dp[i+1][j+1]=dp[i][j]+v[i].second;
par[i+1][j+1]=1;
}
if(j>0 && dp[i][j]-v[i].first>dp[i+1][j-1]) {
dp[i+1][j-1]=dp[i][j]-v[i].first;
par[i+1][j-1]=-1;
}
}
}
vector<int> res;
int cur=N, bal=N/2;
while(cur>0) {
res.push_back(par[cur][bal]);
bal-=par[cur][bal];
cur--;
}
reverse(res.begin(),res.end());
return res;
}
long long find_maximum(int K, std::vector<std::vector<int>> d) {
N=d.size();
M=d[0].size();
for(int i=0;i<N;i++) bk[i]=M-1;
vector<vector<int>> s(N,vector<int>(M,-1));
ll ans=0;
for(int x=0;x<K;x++) {
vector<pair<int,int>> options;
for(int i=0;i<N;i++) {
options.push_back({d[i][fr[i]],d[i][bk[i]]});
}
vector<int> v=work(options);
for(int i=0;i<N;i++) {
if(v[i]>0) {
s[i][bk[i]]=x;
ans+=d[i][bk[i]];
bk[i]--;
} else {
s[i][fr[i]]=x;
ans-=d[i][fr[i]];
fr[i]++;
}
}
}
allocate_tickets(s);
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |