oj.uz

Submission #365174

# Submission time Handle Problem Language Result Execution time Memory
365174 2021-02-11T06:15:38 Z kshitij_sodani Žarulje (COI15_zarulje) C++14
22 / 100
 94 ms 50332 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo n,k;
llo mod=1e9+7;
llo it[200001];
llo dp[2001][2001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	dp[0][n-1]=1;
	for(llo i=n-2;i>=0;i--){
		for(llo j=0;j+i<n;j++){
			dp[j][j+i]=0;
			llo x=0;
			if(j>0){
				x=max(x,it[j-1]);
			}
			if(j+i+1<n){
				x=max(x,it[j+i+1]);
			}
			if(j>0){
				if(it[j-1]==x){
					dp[j][j+i]+=dp[j-1][j+i];
				}
			}
			if(j+i+1<n){
				if(it[j+i+1]==x){
					dp[j][j+i]+=dp[j][j+i+1];
				}
			}
			dp[j][j+i]%=mod;
		}
	}
	vector<llo> ss;
	for(llo i=0;i<k;i++){
		llo aa;
		cin>>aa;
		ss.pb(aa-1);
	}
	for(auto j:ss){
		cout<<dp[j][j]<<endl;
	}







 
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 9 ms 8300 KB Output is correct
3 Correct 36 ms 23148 KB Output is correct
4 Correct 38 ms 23148 KB Output is correct
5 Correct 35 ms 23020 KB Output is correct
6 Correct 36 ms 23148 KB Output is correct

Subtask #2
0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 94 ms 50332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 9 ms 8300 KB Output is correct
3 Correct 36 ms 23148 KB Output is correct
4 Correct 38 ms 23148 KB Output is correct
5 Correct 35 ms 23020 KB Output is correct
6 Correct 36 ms 23148 KB Output is correct
7 Runtime error 94 ms 50332 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -