oj.uz

답안 #250725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250725 2020-07-18T22:36:21 Z WhaleVomit Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 420 ms 774804 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;
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 382 ms 774616 KB Output is correct
2 Correct 369 ms 774704 KB Output is correct
3 Correct 367 ms 774524 KB Output is correct
4 Incorrect 383 ms 774776 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 382 ms 774616 KB Output is correct
2 Correct 369 ms 774704 KB Output is correct
3 Correct 367 ms 774524 KB Output is correct
4 Incorrect 383 ms 774776 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 379 ms 774732 KB Output is correct
2 Correct 369 ms 774648 KB Output is correct
3 Correct 366 ms 774648 KB Output is correct
4 Correct 374 ms 774648 KB Output is correct
5 Correct 388 ms 774648 KB Output is correct
6 Correct 372 ms 774648 KB Output is correct
7 Correct 398 ms 774576 KB Output is correct
8 Correct 382 ms 774804 KB Output is correct
9 Correct 403 ms 774704 KB Output is correct
10 Correct 393 ms 774616 KB Output is correct
11 Correct 418 ms 774648 KB Output is correct
12 Correct 392 ms 774648 KB Output is correct
13 Correct 373 ms 774648 KB Output is correct
14 Correct 383 ms 774648 KB Output is correct
15 Correct 416 ms 774716 KB Output is correct
16 Correct 420 ms 774648 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 382 ms 774616 KB Output is correct
2 Correct 369 ms 774704 KB Output is correct
3 Correct 367 ms 774524 KB Output is correct
4 Incorrect 383 ms 774776 KB Output isn't correct
5 Halted 0 ms 0 KB -