답안 #99707 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99707	2019-03-06T07:45:27 Z	kjp4155	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	187 ms	164336 KB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

#define VA_NUM_ARGS(...) VA_NUM_ARGS_IMPL_((0,__VA_ARGS__, 6,5,4,3,2,1))
#define VA_NUM_ARGS_IMPL_(tuple) VA_NUM_ARGS_IMPL tuple
#define VA_NUM_ARGS_IMPL(_0,_1,_2,_3,_4,_5,_6,N,...) N
#define macro_dispatcher(macro, ...) macro_dispatcher_(macro, VA_NUM_ARGS(__VA_ARGS__))
#define macro_dispatcher_(macro, nargs) macro_dispatcher__(macro, nargs)
#define macro_dispatcher__(macro, nargs) macro_dispatcher___(macro, nargs)
#define macro_dispatcher___(macro, nargs) macro ## nargs
#define Debug1(a)           cout<<#a<<"="<<(a)<<"\n"
#define Debug2(a,b)         cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define Debug3(a,b,c)       cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define Debug4(a,b,c,d)     cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define Debug5(a,b,c,d,e)   cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define Debug6(a,b,c,d,e,f) cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define Debug(...) macro_dispatcher(Debug, __VA_ARGS__)(__VA_ARGS__)
#define DA(a,s,n) cout<<#a<<"=["; printarray(a,s,n); cout<<"]\n"

#define TT1 template<class T>
#define TT1T2 template<class T1, class T2>
#define TT1T2T3 template<class T1, class T2, class T3>
template<class T, size_t N> ostream& operator << (ostream& os, const array<T, N>& v);
TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p){ return os <<"("<<p.first<<", "<< p.second<<")"; }
TT1 ostream& operator << (ostream& os, const vector<T>& v){       bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
template<class T, size_t N> ostream& operator << (ostream& os, const array<T, N>& v) {     bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v){    bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
TT1T2 ostream& operator << (ostream& os, const multiset<T1,T2>&v){bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
TT1T2T3 ostream& operator << (ostream& os, const map<T1,T2,T3>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
TT1T2 ostream& operator << (ostream& os, const multimap<T1, T2>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v) { bool f = 1; os << "["; while (!v.empty()) { auto x = v.top(); v.pop(); if (!f) os << ", "; f = 0; os << x; } return os << "]"; }
TT1T2 void printarray(const T1& a, T2 l, T2 r){ for (T2 i = l; i<=r; i++) cout << a[i] << (i<r?" ":""); }

void cio(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //cout << setprecision(15);
}

#define tt() printf("%.4f sec\n", (double) clock() / CLOCKS_PER_SEC )

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define repp(i, n) for(int i=1;i<=n;i++)
#define all(x) x.begin(), x.end()
#define geti1(X) cin >> X
#define geti2(X,Y) cin >> X >> Y
#define geti3(X,Y,Z) cin >> X >> Y >> Z
#define geti4(X,Y,Z,W) cin >> X >> Y >> Z >> W
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define geti(...) GET_MACRO(__VA_ARGS__, geti4, geti3, geti2, geti1) (__VA_ARGS__)

#define endl '\n'

typedef tuple<int,int,int> t3;
typedef tuple<int,int,int,int> t4;
void die(){printf("-1\n"); exit(0);}
int xx[8] = {1,-1,0,0,1,1,-1,-1}, yy[8] = {0,0,1,-1,1,-1,1,-1};
const ll mod = 1e9+7;

#define MAXN 505
int N, p[MAXN], C[4];
int pos[4][MAXN], idx[4];
char buf[MAXN];
int D[MAXN][MAXN][MAXN][3];
int X[3][MAXN][MAXN], Y[MAXN];

void upd(int& a, int b){ if( a > b ) a = b; }

inline int get(int k, int r, int x){
    return X[k][r][x];
    /*
    int low = 1, high = r, res = -1;
    while( low <= high ){
        int mid = (low+high)/2;
        if( pos[k][mid] > x ) res = mid, high = mid-1;
        else low = mid+1;
    }
    if( res == -1 ) return 0;
    return r - res + 1;
    */
}

int main(){
    scanf("%d",&N); scanf("%s",buf+1);
    repp(i,N){
        if( buf[i] == 'R' ) p[i] = 0, C[0]++;
        if( buf[i] == 'G' ) p[i] = 1, C[1]++;
        if( buf[i] == 'Y' ) p[i] = 2, C[2]++;
    }
    repp(i,N){
        pos[p[i]][++idx[p[i]]] = i;
    }
    for(int k=0;k<3;k++){
        repp(i,N) Y[i] = 0;
        for(int i=1;i<=idx[k];i++){
            for(int j=pos[k][i];j>=1;j--) Y[j]++;
            for(int j=1;j<=N;j++) X[k][i][j] = Y[j];
        }
    }

    rep(i,C[0]+1)rep(j,C[1]+1)rep(k,C[2]+1)rep(l,3) D[i][j][k][l] = 1e9;
    D[0][0][0][0] = D[0][0][0][1] = D[0][0][0][2] = 0;
    int ans = 1e9;
    for(int a=0;a<=C[0];a++)
    for(int b=0;b<=C[1];b++)
    for(int c=0;c<=C[2];c++)
    for(int k=0;k<3;k++){
        int n = a + b + c;
        if( n == N ) ans = min(ans, D[a][b][c][k]);
        //if( D[a][b][c][k] == 0 ) Debug(a,b,c,k);
        if( a+1 <= C[0] && k != 0 ){
            int acc = 0;
            acc += get(1, min(b, idx[1]), pos[0][a+1]);
            acc += get(2, min(c, idx[2]), pos[0][a+1]);
            upd(D[a+1][b][c][0], D[a][b][c][k] + acc);
        }
        if( b+1 <= C[1] && k != 1 ){
            int acc = 0;
            acc += get(0, min(a, idx[0]), pos[1][b+1]);
            acc += get(2, min(c, idx[2]), pos[1][b+1]);
            upd(D[a][b+1][c][1], D[a][b][c][k] + acc);
        }
        if( c+1 <= C[2] && k != 2 ){
            int acc = 0;
            acc += get(0, min(a, idx[0]), pos[2][c+1]);
            acc += get(1, min(b, idx[1]), pos[2][c+1]);
            upd(D[a][b][c+1][2], D[a][b][c][k] + acc);
        }
    }
    if( ans >= 1e9  ) printf("-1\n");
    else printf("%d\n",ans);
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N); scanf("%s",buf+1);
     ~~~~~^~~~~~~~~
joi2019_ho_t3.cpp:94:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N); scanf("%s",buf+1);
                     ~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	412 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	512 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	3 ms	512 KB	Output is correct
9	Correct	2 ms	640 KB	Output is correct
10	Correct	2 ms	640 KB	Output is correct
11	Correct	3 ms	640 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	2 ms	512 KB	Output is correct
15	Correct	2 ms	512 KB	Output is correct
16	Correct	2 ms	512 KB	Output is correct
17	Correct	3 ms	440 KB	Output is correct

Subtask #2
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	412 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	512 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	3 ms	512 KB	Output is correct
9	Correct	2 ms	640 KB	Output is correct
10	Correct	2 ms	640 KB	Output is correct
11	Correct	3 ms	640 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	2 ms	512 KB	Output is correct
15	Correct	2 ms	512 KB	Output is correct
16	Correct	2 ms	512 KB	Output is correct
17	Correct	3 ms	440 KB	Output is correct
18	Correct	5 ms	2432 KB	Output is correct
19	Correct	4 ms	2048 KB	Output is correct
20	Correct	5 ms	2404 KB	Output is correct
21	Correct	5 ms	2560 KB	Output is correct
22	Correct	3 ms	1792 KB	Output is correct
23	Correct	4 ms	2304 KB	Output is correct
24	Correct	4 ms	1792 KB	Output is correct
25	Correct	6 ms	4224 KB	Output is correct
26	Correct	6 ms	4352 KB	Output is correct
27	Correct	5 ms	3200 KB	Output is correct
28	Correct	5 ms	2560 KB	Output is correct
29	Correct	4 ms	2432 KB	Output is correct
30	Correct	4 ms	2432 KB	Output is correct
31	Correct	4 ms	2176 KB	Output is correct
32	Correct	0 ms	2560 KB	Output is correct
33	Correct	6 ms	4096 KB	Output is correct
34	Correct	6 ms	3840 KB	Output is correct
35	Correct	5 ms	2828 KB	Output is correct
36	Correct	4 ms	2052 KB	Output is correct
37	Correct	4 ms	1920 KB	Output is correct
38	Correct	5 ms	2304 KB	Output is correct
39	Correct	4 ms	2432 KB	Output is correct
40	Correct	3 ms	640 KB	Output is correct
41	Correct	4 ms	2432 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	130 ms	164216 KB	Output is correct
3	Correct	131 ms	163420 KB	Output is correct
4	Correct	138 ms	164292 KB	Output is correct
5	Correct	138 ms	164264 KB	Output is correct
6	Correct	138 ms	164216 KB	Output is correct
7	Correct	140 ms	163448 KB	Output is correct
8	Correct	135 ms	163448 KB	Output is correct
9	Correct	133 ms	162592 KB	Output is correct
10	Correct	128 ms	164216 KB	Output is correct
11	Correct	145 ms	164232 KB	Output is correct
12	Correct	43 ms	44664 KB	Output is correct
13	Correct	77 ms	77916 KB	Output is correct
14	Correct	100 ms	112376 KB	Output is correct
15	Correct	139 ms	164188 KB	Output is correct
16	Correct	136 ms	164336 KB	Output is correct

Subtask #4
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	412 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	512 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	3 ms	512 KB	Output is correct
9	Correct	2 ms	640 KB	Output is correct
10	Correct	2 ms	640 KB	Output is correct
11	Correct	3 ms	640 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	2 ms	512 KB	Output is correct
15	Correct	2 ms	512 KB	Output is correct
16	Correct	2 ms	512 KB	Output is correct
17	Correct	3 ms	440 KB	Output is correct
18	Correct	5 ms	2432 KB	Output is correct
19	Correct	4 ms	2048 KB	Output is correct
20	Correct	5 ms	2404 KB	Output is correct
21	Correct	5 ms	2560 KB	Output is correct
22	Correct	3 ms	1792 KB	Output is correct
23	Correct	4 ms	2304 KB	Output is correct
24	Correct	4 ms	1792 KB	Output is correct
25	Correct	6 ms	4224 KB	Output is correct
26	Correct	6 ms	4352 KB	Output is correct
27	Correct	5 ms	3200 KB	Output is correct
28	Correct	5 ms	2560 KB	Output is correct
29	Correct	4 ms	2432 KB	Output is correct
30	Correct	4 ms	2432 KB	Output is correct
31	Correct	4 ms	2176 KB	Output is correct
32	Correct	0 ms	2560 KB	Output is correct
33	Correct	6 ms	4096 KB	Output is correct
34	Correct	6 ms	3840 KB	Output is correct
35	Correct	5 ms	2828 KB	Output is correct
36	Correct	4 ms	2052 KB	Output is correct
37	Correct	4 ms	1920 KB	Output is correct
38	Correct	5 ms	2304 KB	Output is correct
39	Correct	4 ms	2432 KB	Output is correct
40	Correct	3 ms	640 KB	Output is correct
41	Correct	4 ms	2432 KB	Output is correct
42	Correct	2 ms	384 KB	Output is correct
43	Correct	130 ms	164216 KB	Output is correct
44	Correct	131 ms	163420 KB	Output is correct
45	Correct	138 ms	164292 KB	Output is correct
46	Correct	138 ms	164264 KB	Output is correct
47	Correct	138 ms	164216 KB	Output is correct
48	Correct	140 ms	163448 KB	Output is correct
49	Correct	135 ms	163448 KB	Output is correct
50	Correct	133 ms	162592 KB	Output is correct
51	Correct	128 ms	164216 KB	Output is correct
52	Correct	145 ms	164232 KB	Output is correct
53	Correct	43 ms	44664 KB	Output is correct
54	Correct	77 ms	77916 KB	Output is correct
55	Correct	100 ms	112376 KB	Output is correct
56	Correct	139 ms	164188 KB	Output is correct
57	Correct	136 ms	164336 KB	Output is correct
58	Correct	135 ms	93304 KB	Output is correct
59	Correct	187 ms	110556 KB	Output is correct
60	Correct	138 ms	103048 KB	Output is correct
61	Correct	155 ms	100856 KB	Output is correct
62	Correct	152 ms	161884 KB	Output is correct
63	Correct	143 ms	161488 KB	Output is correct
64	Correct	149 ms	151288 KB	Output is correct
65	Correct	169 ms	139788 KB	Output is correct
66	Correct	150 ms	101368 KB	Output is correct
67	Correct	138 ms	98680 KB	Output is correct
68	Correct	165 ms	104048 KB	Output is correct
69	Correct	136 ms	101472 KB	Output is correct
70	Correct	155 ms	107512 KB	Output is correct
71	Correct	127 ms	99428 KB	Output is correct
72	Correct	53 ms	43392 KB	Output is correct
73	Correct	10 ms	4352 KB	Output is correct

답안 #99707

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 55.0 / 55.0

Subtask #3 15.0 / 15.0

Subtask #4 25.0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
55.0 / 55.0

Subtask #3
15.0 / 15.0

Subtask #4
25.0 / 25.0