oj.uz

Submission #250724

# Submission time Handle Problem Language Result Execution time Memory
250724 2020-07-18T22:35:02 Z WhaleVomit Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 494 ms 774776 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;
 
struct chash {
    int operator()(pair<pi, pair<pi,int>> x) const {
        return 31*x.f.f + 17*x.f.s + 3*x.s.f.f + 13*x.s.f.s + 7*x.s.s;
    }
};
 
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) dp[a][b][c][d] = -1;
    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 494 ms 774588 KB Output is correct
2 Correct 407 ms 774524 KB Output is correct
3 Correct 408 ms 774520 KB Output is correct
4 Incorrect 407 ms 774520 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 774588 KB Output is correct
2 Correct 407 ms 774524 KB Output is correct
3 Correct 408 ms 774520 KB Output is correct
4 Incorrect 407 ms 774520 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 412 ms 774636 KB Output is correct
2 Correct 410 ms 774648 KB Output is correct
3 Correct 405 ms 774648 KB Output is correct
4 Correct 413 ms 774648 KB Output is correct
5 Correct 413 ms 774652 KB Output is correct
6 Correct 408 ms 774648 KB Output is correct
7 Correct 427 ms 774776 KB Output is correct
8 Correct 409 ms 774648 KB Output is correct
9 Correct 458 ms 774648 KB Output is correct
10 Correct 406 ms 774648 KB Output is correct
11 Correct 409 ms 774648 KB Output is correct
12 Correct 422 ms 774592 KB Output is correct
13 Correct 413 ms 774648 KB Output is correct
14 Correct 408 ms 774648 KB Output is correct
15 Correct 444 ms 774652 KB Output is correct
16 Correct 423 ms 774776 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 774588 KB Output is correct
2 Correct 407 ms 774524 KB Output is correct
3 Correct 408 ms 774520 KB Output is correct
4 Incorrect 407 ms 774520 KB Output isn't correct
5 Halted 0 ms 0 KB -