oj.uz

Submission #1091997

# Submission time Handle Problem Language Result Execution time Memory
1091997 2024-09-22T19:29:25 Z _rain_ Visiting Singapore (NOI20_visitingsingapore) C++14
10 / 100
 21 ms 856 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define fixbug false
 
const ll INF = (ll)1e18+7;
const int maxn = 5e3;
int K , n , m ;
ll A , B;
int s[maxn+2] , t[maxn+2] ;
ll v[maxn+2];
 
namespace subtaskfull{
	bool check(){
		return true;
	}
	ll sub(int x1 , int x , int y1 , int y){
		// x for T , y for S
		return A*(x1+y1) + B*(y+x);
	}
	// dp[S][T][MATCH/NOT] 
	ll dpcot[maxn+2] , tamcot[maxn+2] , cot[maxn+2];
	ll dgcheo[maxn+2] , tamcheo[maxn+2];
	ll dp[maxn+2] , f[maxn+2];
	ll ngang[maxn+2]={},tamngang[maxn+2];
	void main_code(){
		memset(dpcot,-0x3f,sizeof dpcot);
		memset(dgcheo,-0x3f,sizeof dgcheo);
		memset(dp,-0x3f,sizeof dp);
		memset(ngang,-0x3f,sizeof ngang);
		for (int i = 0; i <= n; ++i) dp[i] = 0;
		ll ans = -INF;
		for (int layer = 1; layer <= m; ++layer) // T for 
		{
			if (fixbug){
				cout << "(DEBUG)\n";
			}
			for (int i = 0; i <= n; ++i){
				tamcheo[i] = dgcheo[i];
				tamcot[i] = dpcot[i];
				tamngang[i] = ngang[i];
				f[i] = dp[i];
				ngang[i] = dpcot[i] = dgcheo[i] = dp[i] = -INF;
			}
			for (int i = 1; i <= n; ++i) // S for 
			{
				if(s[i]==t[layer])
				{
					dp[i] = max({
						f[i - 1],
						tamcot[i - 1] ,	
						cot[i],
						tamcheo[i-1],
						ngang[i-1]
					}) + v[t[layer]];	
				} 	
				dpcot[i] = max({
					dp[i-1] + sub(1,1,0,0),
					max(tamcot[i],dpcot[i-1]) + sub(0,1,0,0),
					f[i] + sub(1,1,0,0)
				});
				dgcheo[i] = max({ 	
					f[i-1] + sub(1,1,1,1),
					tamcheo[i-1] + sub(0,1,0,1)
				});
				ngang[i] = max({
					ngang[i-1] + sub(0,0,0,1),
					tamcheo[i-1] + sub(0,1,0,1),
					dgcheo[i-1] + sub(0,1,0,0),
					f[i-1] + sub(1,1,1,1),
					tamngang[i] + sub(0,0,0,1)
				});
				if (layer==1) cot[i] += sub(1,1,0,0); else cot[i] += sub(0,1,0,0);
				if (fixbug){
					cout << layer << " -- " << i << '\n';
					cout << ngang[i] << ' ' << dpcot[i] << ' ' << dgcheo[i] << ' ' << dp[i] << '\n';
				}
			}
		}
		for (int i = 1; i <= n; ++i) ans = max(ans,dp[i]);
		cout << ans;
	}
}
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	cin >> K >> n >> m >> A >> B;
	for (int i = 1; i <= K; ++i) cin >> v[i];
	for (int i = 1; i <= n; ++i) cin >> s[i];
	for (int i = 1; i <= m; ++i) cin >> t[i];
 
	if (subtaskfull::check()){
		subtaskfull::main_code();
		exit(0);
	}
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 10 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 6 ms 600 KB Output is correct
10 Correct 11 ms 700 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 3 ms 664 KB Output is correct
4 Correct 1 ms 644 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 6 ms 680 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 8 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 12 ms 704 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 10 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 6 ms 600 KB Output is correct
10 Correct 11 ms 700 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 3 ms 664 KB Output is correct
14 Correct 1 ms 644 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 6 ms 680 KB Output is correct
17 Correct 5 ms 604 KB Output is correct
18 Correct 8 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 12 ms 704 KB Output is correct
21 Incorrect 21 ms 600 KB Output isn't correct
22 Halted 0 ms 0 KB -