oj.uz

답안 #97299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97299 2019-02-15T00:22:16 Z RezwanArefin01 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 809548 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 410;
int n, c[3], dp[N][3][N][N], cnt[3], f[3][N]; 
char s[N]; 
vector<int> pos[3]; 

int main(int argc, char const *argv[]) {
    scanf("%d", &n);
    scanf(" %s", s + 1); 
    for(int i = 1; i <= n; ++i) {
        int c = s[i] == 'R' ? 0 : s[i] == 'G' ? 1 : 2; 
        pos[c].push_back(i); 
        ++cnt[c];
    }
    sort(cnt, cnt + 3); 
    sort(pos, pos+3, [](vector<int> &a, vector<int> &b) { return a.size() < b.size(); }); 
    for(int i = 0; i <= 2; ++i) {
        for(int x : pos[i]) f[i][x] = 1; 
        for(int j = n - 1; j >= 0; --j) 
            f[i][j] += f[i][j + 1]; 
    }

    memset(dp, 63, sizeof dp); 
    memset(dp[1], 0, sizeof dp[1]); 

    for(int i = 1; i <= n; ++i) {
        for(int p = 0; p <= 2; ++p) {
            for(c[0] = 0; c[0] < i && c[0] <= cnt[0]; ++c[0]) {
                for(c[1] = 0; c[1] < i - c[0] && c[1] <= cnt[1]; ++c[1]) {
                    c[2] = i - c[0] - c[1] - 1; 
                    if(c[2] > cnt[2]) continue; 
                    
                    for(int q = 0; q <= 2; ++q) if(p != q && c[q] != cnt[q]) {
                        int idx = pos[q][c[q]];
                        idx += max(0, c[p] - cnt[p] + f[p][idx]) + 
                        	   max(0, c[p^q^3] - cnt[p^q^3] + f[p^q^3][idx]); 

                        int &x = dp[i + 1][q][q == 0 ? c[0] + 1 : c[0]][q == 1 ? c[1] + 1 : c[1]];
                        x = min(x, dp[i][p][c[0]][c[1]] + abs(idx - i)); 
                    }
                }
            }
        }
    }

    int ans = 1e9;  
    for(int i = 0; i <= 2; i++) ans = min(ans, dp[n + 1][i][cnt[0]][cnt[1]]); 
    if(ans >= 1e9) ans = -1;
    printf("%d\n", ans); 
}

Compilation message

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

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1251 ms 799944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1251 ms 799944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 770 ms 809548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1251 ms 799944 KB Time limit exceeded
2 Halted 0 ms 0 KB -