oj.uz

Submission #1072693

# Submission time Handle Problem Language Result Execution time Memory
1072693 2024-08-24T02:57:49 Z LCJLY Carnival Tickets (IOI20_tickets) C++14
0 / 100
 1 ms 4444 KB 
#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];
	}
	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]=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);
		pii hold={-1,-1};
		for(int y=0;y<m;y++){
			hold=max(hold,{arr[x][y],y});
		}
		maxi.push_back(hold);
		hold={1e15,1e15};
		for(int y=0;y<m;y++){
			hold=min(hold,{arr[x][y],y});
		}
		mini.push_back(hold);
	}
	pii cur={0,n2};
	int 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]=0;
		else ans[x][maxi[x].second]=0;
		cur=nxt;
	}
	allocate_tickets(ans);
	return take;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Contestant returned 298620960 but the tickets gives a total value of 500507564
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 4444 KB Contestant returned 786069791 but the tickets gives a total value of 2930223109
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB There is no ticket of color 0 on day 1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB There is no ticket of color 0 on day 1
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB There is no ticket of color 0 on day 1
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB There is no ticket of color 0 on day 1
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Contestant returned 298620960 but the tickets gives a total value of 500507564
2 Halted 0 ms 0 KB -