Submission #1094334

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1094334	2024-09-29T10:46:40 Z	blacktulip	Art Exhibition (JOI18_art)	C++17	30 / 100	1000 ms	262144 KB

art

#include <bits/stdc++.h>

using namespace std;

typedef long long lo; 

#define fi first
#define se second
#define endl "\n"
#define pb push_back
#define int long long
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
#define _ << " " <<

const lo inf = 1000000000;
const lo li = 305;
const lo mod = 1000000007;

int n,m,a[li],k,flag,t,b[li],dp[li][li][li];
int cev;
string s;
vector<int> v;

inline int f(int i,int maxi,int mini){
	int cevap=-1000000000000000000;
	if(i>n){
		return -(a[maxi]-a[mini]);
	}
	if(~dp[i][maxi][mini])return dp[i][maxi][mini];
	cevap=max(cevap,f(i+1,maxi,mini));
	int tmax=maxi;
	if(maxi==0 || a[i]>a[maxi])tmax=i;
	int tmin=mini;
	if(mini==0 || a[i]<a[mini])tmin=i;
	cevap=max(cevap,f(i+1,tmax,tmin)+b[i]);
	//~ cout<<maxi _ mini _ i <<endl;
	return dp[i][maxi][mini]=cevap;
}

int32_t main(void){
	fio();
	cin>>n;
	memset(dp,-1,sizeof(dp));
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}
	cout<<f(1,0,0)<<endl;
	return 0;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	222460 KB	Output is correct
2	Correct	93 ms	222544 KB	Output is correct
3	Correct	95 ms	222464 KB	Output is correct
4	Correct	97 ms	222396 KB	Output is correct
5	Correct	95 ms	222292 KB	Output is correct
6	Correct	92 ms	222292 KB	Output is correct
7	Correct	93 ms	222288 KB	Output is correct
8	Correct	96 ms	222300 KB	Output is correct
9	Correct	93 ms	222304 KB	Output is correct
10	Correct	93 ms	222292 KB	Output is correct
11	Correct	93 ms	222292 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	222460 KB	Output is correct
2	Correct	93 ms	222544 KB	Output is correct
3	Correct	95 ms	222464 KB	Output is correct
4	Correct	97 ms	222396 KB	Output is correct
5	Correct	95 ms	222292 KB	Output is correct
6	Correct	92 ms	222292 KB	Output is correct
7	Correct	93 ms	222288 KB	Output is correct
8	Correct	96 ms	222300 KB	Output is correct
9	Correct	93 ms	222304 KB	Output is correct
10	Correct	93 ms	222292 KB	Output is correct
11	Correct	93 ms	222292 KB	Output is correct
12	Correct	141 ms	222524 KB	Output is correct
13	Correct	144 ms	222548 KB	Output is correct
14	Correct	139 ms	222392 KB	Output is correct
15	Correct	150 ms	222548 KB	Output is correct
16	Correct	156 ms	222316 KB	Output is correct
17	Correct	155 ms	222488 KB	Output is correct
18	Correct	159 ms	222544 KB	Output is correct
19	Correct	163 ms	222544 KB	Output is correct
20	Correct	156 ms	222544 KB	Output is correct
21	Correct	162 ms	222544 KB	Output is correct
22	Correct	155 ms	222548 KB	Output is correct
23	Correct	159 ms	222548 KB	Output is correct
24	Correct	156 ms	222504 KB	Output is correct
25	Correct	156 ms	222544 KB	Output is correct
26	Correct	152 ms	222544 KB	Output is correct

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	222460 KB	Output is correct
2	Correct	93 ms	222544 KB	Output is correct
3	Correct	95 ms	222464 KB	Output is correct
4	Correct	97 ms	222396 KB	Output is correct
5	Correct	95 ms	222292 KB	Output is correct
6	Correct	92 ms	222292 KB	Output is correct
7	Correct	93 ms	222288 KB	Output is correct
8	Correct	96 ms	222300 KB	Output is correct
9	Correct	93 ms	222304 KB	Output is correct
10	Correct	93 ms	222292 KB	Output is correct
11	Correct	93 ms	222292 KB	Output is correct
12	Correct	141 ms	222524 KB	Output is correct
13	Correct	144 ms	222548 KB	Output is correct
14	Correct	139 ms	222392 KB	Output is correct
15	Correct	150 ms	222548 KB	Output is correct
16	Correct	156 ms	222316 KB	Output is correct
17	Correct	155 ms	222488 KB	Output is correct
18	Correct	159 ms	222544 KB	Output is correct
19	Correct	163 ms	222544 KB	Output is correct
20	Correct	156 ms	222544 KB	Output is correct
21	Correct	162 ms	222544 KB	Output is correct
22	Correct	155 ms	222548 KB	Output is correct
23	Correct	159 ms	222548 KB	Output is correct
24	Correct	156 ms	222504 KB	Output is correct
25	Correct	156 ms	222544 KB	Output is correct
26	Correct	152 ms	222544 KB	Output is correct
27	Execution timed out	2271 ms	262144 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #4

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	222460 KB	Output is correct
2	Correct	93 ms	222544 KB	Output is correct
3	Correct	95 ms	222464 KB	Output is correct
4	Correct	97 ms	222396 KB	Output is correct
5	Correct	95 ms	222292 KB	Output is correct
6	Correct	92 ms	222292 KB	Output is correct
7	Correct	93 ms	222288 KB	Output is correct
8	Correct	96 ms	222300 KB	Output is correct
9	Correct	93 ms	222304 KB	Output is correct
10	Correct	93 ms	222292 KB	Output is correct
11	Correct	93 ms	222292 KB	Output is correct
12	Correct	141 ms	222524 KB	Output is correct
13	Correct	144 ms	222548 KB	Output is correct
14	Correct	139 ms	222392 KB	Output is correct
15	Correct	150 ms	222548 KB	Output is correct
16	Correct	156 ms	222316 KB	Output is correct
17	Correct	155 ms	222488 KB	Output is correct
18	Correct	159 ms	222544 KB	Output is correct
19	Correct	163 ms	222544 KB	Output is correct
20	Correct	156 ms	222544 KB	Output is correct
21	Correct	162 ms	222544 KB	Output is correct
22	Correct	155 ms	222548 KB	Output is correct
23	Correct	159 ms	222548 KB	Output is correct
24	Correct	156 ms	222504 KB	Output is correct
25	Correct	156 ms	222544 KB	Output is correct
26	Correct	152 ms	222544 KB	Output is correct
27	Execution timed out	2271 ms	262144 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-