oj.uz

Submission #1004798

# Submission time Handle Problem Language Result Execution time Memory
1004798 2024-06-21T15:55:03 Z DangerNoodle7591 Kamenčići (COCI21_kamencici) C++17
70 / 70
 22 ms 84828 KB 
#include  <bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
//#define int long long int
//#define ll long long
#define pb push_back
#define p push
#define f first
#define s second
#define N 350
int arr[N];
int dp[N][N][N/2+1];//l r biz_kaç_red
int n,k;
inline int red_blue(int l,int r,int biz,int o,int sira){
  if(dp[l][r][biz]!=-1)return dp[l][r][biz];
  if(biz==k)return 0;
  if(o==k)return 1;
  if(sira){//bizde
    int sol=red_blue(l,r-1,biz+arr[r],o,0),sag=red_blue(l+1,r,biz+arr[l],o,0);
    dp[l][r][biz]=max(sag,sol);
    return dp[l][r][biz];
  }

  int sol=red_blue(l,r-1,biz,o+arr[r],1),sag=red_blue(l+1,r,biz,o+arr[l],1);
  dp[l][r][biz]=min(sol,sag);
  return dp[l][r][biz];
}
signed main(){
  lalala;
  cin>>n>>k;
  for(int i=0;i<n;i++){
    char a;cin>>a;
    if(a=='C') arr[i]=1;
  }
  memset(dp,-1,sizeof(dp));
  int a=red_blue(0,n-1,0,0,1);
  if(a)cout<<"DA"<<endl;
  else cout<<"NE"<<endl;
 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 84824 KB Output is correct
2 Correct 11 ms 84828 KB Output is correct
3 Correct 11 ms 84764 KB Output is correct
4 Correct 11 ms 84828 KB Output is correct
5 Correct 10 ms 84828 KB Output is correct
6 Correct 11 ms 84828 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 84824 KB Output is correct
2 Correct 11 ms 84828 KB Output is correct
3 Correct 11 ms 84764 KB Output is correct
4 Correct 11 ms 84828 KB Output is correct
5 Correct 10 ms 84828 KB Output is correct
6 Correct 11 ms 84828 KB Output is correct
7 Correct 11 ms 84828 KB Output is correct
8 Correct 11 ms 84688 KB Output is correct
9 Correct 11 ms 84828 KB Output is correct
10 Correct 12 ms 84828 KB Output is correct
11 Correct 11 ms 84828 KB Output is correct
12 Correct 11 ms 84828 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 84824 KB Output is correct
2 Correct 11 ms 84828 KB Output is correct
3 Correct 11 ms 84764 KB Output is correct
4 Correct 11 ms 84828 KB Output is correct
5 Correct 10 ms 84828 KB Output is correct
6 Correct 11 ms 84828 KB Output is correct
7 Correct 11 ms 84828 KB Output is correct
8 Correct 11 ms 84688 KB Output is correct
9 Correct 11 ms 84828 KB Output is correct
10 Correct 12 ms 84828 KB Output is correct
11 Correct 11 ms 84828 KB Output is correct
12 Correct 11 ms 84828 KB Output is correct
13 Correct 12 ms 84828 KB Output is correct
14 Correct 21 ms 84704 KB Output is correct
15 Correct 14 ms 84828 KB Output is correct
16 Correct 22 ms 84828 KB Output is correct
17 Correct 15 ms 84828 KB Output is correct
18 Correct 12 ms 84828 KB Output is correct