oj.uz

Submission #250727

# Submission time Handle Problem Language Result Execution time Memory
250727 2020-07-18T22:55:14 Z WhaleVomit Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 473 ms 774780 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
 
#define MOO(i, a, b) for(int i=a; i<b; i++)
#define M00(i, a) for(int i=0; i<a; i++)
#define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--)
#define M00d(i,a) for(int i = (a)-1; i>=0; i--)
 
#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << '\n', 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _ << " _ " <<
 
template<class T> bool ckmin(T& a, const T& b) {return b < a ? a = b, 1 : 0;}
template<class T> bool ckmax(T& a, const T& b) {return a < b ? a = b, 1 : 0;}
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;
 
const int MAX_N = 404;
int n;
int arr[MAX_N];
int pref[MAX_N][3];
vi idxOf[3];
int dp[MAX_N][3][MAX_N][MAX_N];
 
int getOf(int idx, pair<pi,int> fucked) {
    if(idx == 0) return fucked.f.f;
    if(idx == 1) return fucked.f.s;
    return fucked.s;
}
 
int getcost(int c, pair<pi,int> cnt) { // cost to get the next c
    if(getOf(c, cnt) >= sz(idxOf[c])) return 1e8; // impossible
    int idx = idxOf[c][getOf(c, cnt)];
    int res = idx;
    M00(k, 3) res -= min(getOf(k, cnt), pref[idx][k]);
    return res;
}
 
int getdp(int idx, int c, pair<pi,int> cnt) {
    if(dp[idx][c][cnt.f.f][cnt.f.s] != -1) return dp[idx][c][cnt.f.f][cnt.f.s];
    int cost = getcost(c, cnt);
    if(cost == 1e8) {
        dp[idx][c][cnt.f.f][cnt.f.s] = 1e8;
        return dp[idx][c][cnt.f.f][cnt.f.s]; 
    }
    if(idx == n-1) {
        dp[idx][c][cnt.f.f][cnt.f.s] = cost;
        return dp[idx][c][cnt.f.f][cnt.f.s];
    }
    if(c == 0) {
        cnt.f.f++;
    } else if(c == 1) {
        cnt.f.s++;
    } else {
        cnt.s++;
    }
    int res = 1e8;
    M00(c2, 3) if(c2 != c) {
        ckmin(res, cost + getdp(idx+1, c2, cnt));
    }
    dp[idx][c][cnt.f.f][cnt.f.s] = res;
    return dp[idx][c][cnt.f.f][cnt.f.s];
}
 
int main() { FAST
    //M00(a, MAX_N) M00(b, 3) M00(c, MAX_N) M00(d, MAX_N-c) dp[a][b][c][d] = -1;
    memset(dp, -1, sizeof(dp[0][0][0][0])*MAX_N*3*MAX_N*MAX_N);
    string s;
    cin >> n >> s;
    M00(i, n) {
        if(s[i] == 'R') arr[i] = 0;
        else if(s[i] == 'Y') arr[i] = 1;
        else arr[i] = 2;
    }
    M00(c, 3) {
        pref[0][c] = (arr[0] == c);
        MOO(i, 1, n) pref[i][c] = pref[i-1][c] + (arr[i] == c);
    }
    M00(i, n) idxOf[arr[i]].pb(i);
    int res = 1e8;
    M00(i, 3) ckmin(res, getdp(0, i, mp(mp(0,0),0)));
    if(res == 1e8) {
        finish(-1);
    }
    finish(res);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 774648 KB Output is correct
2 Correct 387 ms 774648 KB Output is correct
3 Correct 388 ms 774780 KB Output is correct
4 Incorrect 401 ms 774524 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 774648 KB Output is correct
2 Correct 387 ms 774648 KB Output is correct
3 Correct 388 ms 774780 KB Output is correct
4 Incorrect 401 ms 774524 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 774596 KB Output is correct
2 Correct 377 ms 774652 KB Output is correct
3 Correct 374 ms 774648 KB Output is correct
4 Correct 377 ms 774648 KB Output is correct
5 Correct 376 ms 774648 KB Output is correct
6 Correct 377 ms 774648 KB Output is correct
7 Correct 375 ms 774648 KB Output is correct
8 Correct 377 ms 774648 KB Output is correct
9 Correct 385 ms 774648 KB Output is correct
10 Correct 382 ms 774648 KB Output is correct
11 Correct 387 ms 774648 KB Output is correct
12 Correct 406 ms 774580 KB Output is correct
13 Correct 421 ms 774648 KB Output is correct
14 Correct 403 ms 774776 KB Output is correct
15 Correct 473 ms 774648 KB Output is correct
16 Correct 401 ms 774648 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 774648 KB Output is correct
2 Correct 387 ms 774648 KB Output is correct
3 Correct 388 ms 774780 KB Output is correct
4 Incorrect 401 ms 774524 KB Output isn't correct
5 Halted 0 ms 0 KB -