| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1072703 | LCJLY | Carnival Tickets (IOI20_tickets) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "tickets.h"
#include "grader.cpp"
using namespace std;
#define int long long
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,long long>pii;
typedef pair<long long,pii>pi2;
//allocate_tickets(vector<vector<int>>)
vector<pii>maxi;
vector<pii>mini;
int n2;
int memo[1505][3005];
bool visited[1505][3005];
pii pp[1505][3005];
int dp(int index, int cur){
if(index==n2){
if(cur==0) return 0;
else return -1e15;
}
if(visited[index][cur+n2]){
return memo[index][cur+n2];
}
//show2(index,index,cur,cur);
int ans=-1e15;
int hold=dp(index+1,cur+1)-mini[index].first;
if(hold>=ans){
ans=hold;
pp[index][cur+n2]={index+1,cur+n2+1};
}
hold=dp(index+1,cur-1)+maxi[index].first;
if(hold>=ans){
ans=hold;
pp[index][cur+n2]={index+1,cur+n2-1};
}
visited[index][cur+n2]=true;
return memo[index][cur+n2]=ans;
}
long long find_maximum(int32_t k, vector<vector<int32_t>>arr){
int n=arr.size();
n2=n;
int m=arr[0].size();
//k==1
vector<vector<int32_t>>ans;
ans.resize(n);
for(int x=0;x<n;x++) ans[x]=vector<int32_t>(m,-1);
int take=0;
for(int i=0;i<k;i++){
//memset array
for(int x=0;x<=n;x++){
for(int y=0;y<=2*n;y++){
visited[x][y]=0;
}
}
maxi.clear();
mini.clear();
for(int x=0;x<n;x++){
pii hold={-1,-1};
for(int y=0;y<m;y++){
if(ans[x][y]!=-1) continue;
hold=max(hold,{arr[x][y],y});
}
maxi.push_back(hold);
hold={1e15,1e15};
for(int y=0;y<m;y++){
if(ans[x][y]!=-1) continue;
hold=min(hold,{arr[x][y],y});
}
mini.push_back(hold);
}
pii cur={0,n2};
take+=dp(0,0);
for(int x=0;x<n;x++){
pii nxt=pp[cur.first][cur.second];
//cout << nxt.first << " " << nxt.second << endl;
if(nxt.second>cur.second) ans[x][mini[x].second]=i;
else ans[x][maxi[x].second]=i;
cur=nxt;
}
//show(done,i);
}
allocate_tickets(ans);
return take;
}