oj.uz

Submission #924077

# Submission time Handle Problem Language Result Execution time Memory
924077 2024-02-08T11:39:47 Z MercubytheFirst Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 475 ms 757860 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
const ll N = 105;
const ll inf = 1e9 + 37;
#define endl '\n'

/*
- have fun!
- monovariants?
- invariants?
- bs on ans?
- phrase it differently?
- quirky constraints? 
- dp? 
- greedy? 
- find slow solution and try to optimize?
*/

void solve(void){
  int n;
  string s;
  cin >> n >> s;
  s = "0" + s;
  for(int i = 1; i <= n; ++i){
    if(s[i] == 'R') s[i] = 0;
    else if(s[i] == 'G') s[i] = 1;
    else if(s[i] == 'Y') s[i] = 2;
  }
  vector<int> k[3];
  k[0].pb(0);
  k[1].pb(0);
  k[2].pb(0);
  for(int i = 1; i <= n; ++i)
    k[(int)s[i]].push_back(i);
  vector<array<int, 3> > pre(n + 1, array<int, 3>{0, 0, 0});
  for(int i = 1; i <= n; ++i){
    pre[i] = pre[i - 1];
    pre[i][s[i]]++;
  }
  int dp[n + 1][n + 1][n + 1][3];
  for(int r = 0; r <= n; ++r)
    for(int g = 0; g <= n; ++g)
      for(int y = 0; y <= n; ++y)
        for(int c = 0; c <3; ++c)
          dp[r][g][y][c] = inf;
  dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
  int c[3] = {0};
  // cout << pre[n][0] << ' ' << pre[n][1] << ' ' << pre[n][2] << endl;
  for(c[0] = 0; c[0] <= pre[n][0]; ++c[0]){
    for(c[1] = 0; c[1] <= pre[n][1]; ++c[1]){
      for(c[2] = 0; c[2] <= pre[n][2]; ++c[2]){
        for(int col = 0; col <3; ++col){
          if(!c[0] and !c[1] and !c[2])
            continue;
          int& ans = dp[c[0]][c[1]][c[2]][col];
          if(c[col] <= 0){
            // cout << c[0] << ' ' << c[1] << ' ' << c[2] << ' ' << col << endl;
            continue;
          }
          // cout << c[0] << ' ' << c[1] << ' ' << c[2] << ' ' << col << endl;
          int i = c[0] + c[1] + c[2];
          int ni = k[col][c[col]], d = 0;
          for(int j = 0; j <3 ; ++j){
            if(j == col)
              continue;
            d += (pre[ni][j] >= c[j] ? 0 : c[j] - pre[ni][j]);
          }
          ni += d;
          for(int j = 0; j <3; ++j){
            if(j == col)
              continue;
            ans = min(ans, dp[c[0] - (col == 0)][c[1] - (col == 1)][c[2] - (col == 2)][j] + ni - i);
          }
        }
      }
    }
  }
  int ans = inf;
  for(int i = 0; i < 3; ++i){
    ans = min(ans, dp[pre[n][0]][pre[n][1]][pre[n][2]][i]);
    // cout << dp[pre[n][0]][pre[n][1]][pre[n][2]][i] << ' ';
  }
  cout << ans << endl;
}

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  // signed t; cin >> t; while(t--)
    solve();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 1 ms 456 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 1 ms 456 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 475 ms 757548 KB Output is correct
3 Correct 427 ms 751860 KB Output is correct
4 Correct 426 ms 757860 KB Output is correct
5 Correct 424 ms 757328 KB Output is correct
6 Correct 429 ms 757412 KB Output is correct
7 Correct 433 ms 752016 KB Output is correct
8 Correct 427 ms 751864 KB Output is correct
9 Correct 428 ms 746064 KB Output is correct
10 Correct 433 ms 757328 KB Output is correct
11 Correct 431 ms 757620 KB Output is correct
12 Correct 63 ms 104528 KB Output is correct
13 Correct 146 ms 244560 KB Output is correct
14 Correct 250 ms 426068 KB Output is correct
15 Incorrect 428 ms 757548 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 1 ms 456 KB Output isn't correct
11 Halted 0 ms 0 KB -