| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 704067 | 2023-03-01T13:42:20 Z | WeIlIaN | Growing Vegetable is Fun 3 (JOI19_ho_t3) | C++14 | 69 ms | 162812 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <climits>
using namespace std;
#define MOD 1000000007
#define fir first
#define sec second
#define push_f push_front
#define push_b push_back
#define pop_f pop_front
#define pop_b pop_back
#define mp make_pair
#define FOR(i, s, e, p) for(int i = s; i < e; i += p)
#define REP(i, n) FOR(i, 0, n, 1)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vpii> vvpii;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef deque<int> dqi;
typedef deque<ll> dqll;
typedef deque<pii> dqpii;
typedef deque<pll> dqpll;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pqll;
typedef priority_queue<pii> pqpii;
typedef priority_queue<pll> pqpll;
typedef priority_queue<int, vi, greater<int> > r_pqi;
typedef priority_queue<ll, vll, greater<ll> > r_pqll;
typedef priority_queue<pii, vpii, greater<pii> > r_pqpii;
typedef priority_queue<pll, vpll, greater<pll> > r_pqpll;
const int INF = 1e9;
int dp[444][444][444][3], len[444][3];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
string s;
cin >> n >> s;
vector<int> r, g, y;
REP(i, n) {
if(s[i] == 'R') r.push_back(i);
if(s[i] == 'G') g.push_back(i);
if(s[i] == 'Y') y.push_back(i);
len[i][0] = r.size();
len[i][1] = g.size();
len[i][2] = y.size();
}
//dp[i][j][k][x] means operations needed to achieve the first i+j+k elements contain i 'R', j 'G', and k 'Y' and the last element is x
REP(i, r.size()+1)
REP(j, g.size()+1)
REP(k, y.size()+1) {
if(!i && !j && !k) {
REP(l, 3) dp[0][0][0][l] = 0;
}
else {
REP(l, 3) dp[i][j][k][l] = INF;
}
int sum = i + j + k;
if(i) {
dp[i][j][k][0] = min(dp[i-1][j][k][1], dp[i-1][j][k][2]) + (r[i-1]+1 + max(0, j-len[r[i-1]][1]) + max(0, k-len[r[i-1]][2]) - sum);
}
if(j) {
dp[i][j][k][1] = min(dp[i][j-1][k][0], dp[i][j-1][k][2]) + (g[j-1]+1 + max(0, i-len[g[j-1]][0]) + max(0, k-len[g[j-1]][2]) - sum);
}
if(k) {
dp[i][j][k][2] = min(dp[i][j][k-1][0], dp[i][j][k-1][1]) + (y[k-1]+1 + max(0, i-len[y[k-1]][0]) + max(0, j-len[y[k-1]][1]) - sum);
}
}
int ans = INF;
REP(i, 3) {
ans = min(ans, dp[r.size()][g.size()][y.size()][i]);
}
cout << (ans >= INF ? -1 : ans);
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 0 ms | 340 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 340 KB | Output is correct |
| 5 | Correct | 1 ms | 340 KB | Output is correct |
| 6 | Correct | 1 ms | 468 KB | Output is correct |
| 7 | Correct | 1 ms | 468 KB | Output is correct |
| 8 | Correct | 1 ms | 468 KB | Output is correct |
| 9 | Correct | 1 ms | 596 KB | Output is correct |
| 10 | Correct | 1 ms | 596 KB | Output is correct |
| 11 | Correct | 1 ms | 468 KB | Output is correct |
| 12 | Correct | 1 ms | 468 KB | Output is correct |
| 13 | Correct | 0 ms | 340 KB | Output is correct |
| 14 | Correct | 0 ms | 468 KB | Output is correct |
| 15 | Correct | 0 ms | 340 KB | Output is correct |
| 16 | Correct | 1 ms | 340 KB | Output is correct |
| 17 | Correct | 0 ms | 340 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 0 ms | 340 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 340 KB | Output is correct |
| 5 | Correct | 1 ms | 340 KB | Output is correct |
| 6 | Correct | 1 ms | 468 KB | Output is correct |
| 7 | Correct | 1 ms | 468 KB | Output is correct |
| 8 | Correct | 1 ms | 468 KB | Output is correct |
| 9 | Correct | 1 ms | 596 KB | Output is correct |
| 10 | Correct | 1 ms | 596 KB | Output is correct |
| 11 | Correct | 1 ms | 468 KB | Output is correct |
| 12 | Correct | 1 ms | 468 KB | Output is correct |
| 13 | Correct | 0 ms | 340 KB | Output is correct |
| 14 | Correct | 0 ms | 468 KB | Output is correct |
| 15 | Correct | 0 ms | 340 KB | Output is correct |
| 16 | Correct | 1 ms | 340 KB | Output is correct |
| 17 | Correct | 0 ms | 340 KB | Output is correct |
| 18 | Correct | 1 ms | 2260 KB | Output is correct |
| 19 | Correct | 1 ms | 1876 KB | Output is correct |
| 20 | Correct | 1 ms | 2260 KB | Output is correct |
| 21 | Correct | 1 ms | 2376 KB | Output is correct |
| 22 | Correct | 1 ms | 1620 KB | Output is correct |
| 23 | Correct | 1 ms | 2132 KB | Output is correct |
| 24 | Correct | 1 ms | 1620 KB | Output is correct |
| 25 | Correct | 2 ms | 3924 KB | Output is correct |
| 26 | Correct | 2 ms | 4180 KB | Output is correct |
| 27 | Correct | 2 ms | 3020 KB | Output is correct |
| 28 | Correct | 1 ms | 2260 KB | Output is correct |
| 29 | Correct | 1 ms | 2260 KB | Output is correct |
| 30 | Correct | 1 ms | 2260 KB | Output is correct |
| 31 | Correct | 1 ms | 1992 KB | Output is correct |
| 32 | Correct | 2 ms | 2388 KB | Output is correct |
| 33 | Correct | 2 ms | 3796 KB | Output is correct |
| 34 | Correct | 2 ms | 3528 KB | Output is correct |
| 35 | Correct | 2 ms | 2644 KB | Output is correct |
| 36 | Correct | 1 ms | 1860 KB | Output is correct |
| 37 | Correct | 1 ms | 1748 KB | Output is correct |
| 38 | Correct | 1 ms | 2128 KB | Output is correct |
| 39 | Correct | 1 ms | 2260 KB | Output is correct |
| 40 | Correct | 1 ms | 328 KB | Output is correct |
| 41 | Correct | 2 ms | 2176 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 340 KB | Output is correct |
| 2 | Correct | 57 ms | 162764 KB | Output is correct |
| 3 | Correct | 56 ms | 162012 KB | Output is correct |
| 4 | Correct | 56 ms | 162792 KB | Output is correct |
| 5 | Correct | 60 ms | 162704 KB | Output is correct |
| 6 | Correct | 58 ms | 162764 KB | Output is correct |
| 7 | Correct | 57 ms | 162024 KB | Output is correct |
| 8 | Correct | 57 ms | 161980 KB | Output is correct |
| 9 | Correct | 56 ms | 161104 KB | Output is correct |
| 10 | Correct | 60 ms | 162812 KB | Output is correct |
| 11 | Correct | 57 ms | 162792 KB | Output is correct |
| 12 | Correct | 16 ms | 43984 KB | Output is correct |
| 13 | Correct | 31 ms | 77076 KB | Output is correct |
| 14 | Correct | 41 ms | 111208 KB | Output is correct |
| 15 | Correct | 57 ms | 162748 KB | Output is correct |
| 16 | Correct | 57 ms | 162764 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 0 ms | 340 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 340 KB | Output is correct |
| 5 | Correct | 1 ms | 340 KB | Output is correct |
| 6 | Correct | 1 ms | 468 KB | Output is correct |
| 7 | Correct | 1 ms | 468 KB | Output is correct |
| 8 | Correct | 1 ms | 468 KB | Output is correct |
| 9 | Correct | 1 ms | 596 KB | Output is correct |
| 10 | Correct | 1 ms | 596 KB | Output is correct |
| 11 | Correct | 1 ms | 468 KB | Output is correct |
| 12 | Correct | 1 ms | 468 KB | Output is correct |
| 13 | Correct | 0 ms | 340 KB | Output is correct |
| 14 | Correct | 0 ms | 468 KB | Output is correct |
| 15 | Correct | 0 ms | 340 KB | Output is correct |
| 16 | Correct | 1 ms | 340 KB | Output is correct |
| 17 | Correct | 0 ms | 340 KB | Output is correct |
| 18 | Correct | 1 ms | 2260 KB | Output is correct |
| 19 | Correct | 1 ms | 1876 KB | Output is correct |
| 20 | Correct | 1 ms | 2260 KB | Output is correct |
| 21 | Correct | 1 ms | 2376 KB | Output is correct |
| 22 | Correct | 1 ms | 1620 KB | Output is correct |
| 23 | Correct | 1 ms | 2132 KB | Output is correct |
| 24 | Correct | 1 ms | 1620 KB | Output is correct |
| 25 | Correct | 2 ms | 3924 KB | Output is correct |
| 26 | Correct | 2 ms | 4180 KB | Output is correct |
| 27 | Correct | 2 ms | 3020 KB | Output is correct |
| 28 | Correct | 1 ms | 2260 KB | Output is correct |
| 29 | Correct | 1 ms | 2260 KB | Output is correct |
| 30 | Correct | 1 ms | 2260 KB | Output is correct |
| 31 | Correct | 1 ms | 1992 KB | Output is correct |
| 32 | Correct | 2 ms | 2388 KB | Output is correct |
| 33 | Correct | 2 ms | 3796 KB | Output is correct |
| 34 | Correct | 2 ms | 3528 KB | Output is correct |
| 35 | Correct | 2 ms | 2644 KB | Output is correct |
| 36 | Correct | 1 ms | 1860 KB | Output is correct |
| 37 | Correct | 1 ms | 1748 KB | Output is correct |
| 38 | Correct | 1 ms | 2128 KB | Output is correct |
| 39 | Correct | 1 ms | 2260 KB | Output is correct |
| 40 | Correct | 1 ms | 328 KB | Output is correct |
| 41 | Correct | 2 ms | 2176 KB | Output is correct |
| 42 | Correct | 0 ms | 340 KB | Output is correct |
| 43 | Correct | 57 ms | 162764 KB | Output is correct |
| 44 | Correct | 56 ms | 162012 KB | Output is correct |
| 45 | Correct | 56 ms | 162792 KB | Output is correct |
| 46 | Correct | 60 ms | 162704 KB | Output is correct |
| 47 | Correct | 58 ms | 162764 KB | Output is correct |
| 48 | Correct | 57 ms | 162024 KB | Output is correct |
| 49 | Correct | 57 ms | 161980 KB | Output is correct |
| 50 | Correct | 56 ms | 161104 KB | Output is correct |
| 51 | Correct | 60 ms | 162812 KB | Output is correct |
| 52 | Correct | 57 ms | 162792 KB | Output is correct |
| 53 | Correct | 16 ms | 43984 KB | Output is correct |
| 54 | Correct | 31 ms | 77076 KB | Output is correct |
| 55 | Correct | 41 ms | 111208 KB | Output is correct |
| 56 | Correct | 57 ms | 162748 KB | Output is correct |
| 57 | Correct | 57 ms | 162764 KB | Output is correct |
| 58 | Correct | 48 ms | 83468 KB | Output is correct |
| 59 | Correct | 60 ms | 105812 KB | Output is correct |
| 60 | Correct | 69 ms | 96192 KB | Output is correct |
| 61 | Correct | 53 ms | 92928 KB | Output is correct |
| 62 | Correct | 58 ms | 160400 KB | Output is correct |
| 63 | Correct | 59 ms | 159996 KB | Output is correct |
| 64 | Correct | 62 ms | 150244 KB | Output is correct |
| 65 | Correct | 62 ms | 138496 KB | Output is correct |
| 66 | Correct | 60 ms | 94244 KB | Output is correct |
| 67 | Correct | 50 ms | 90808 KB | Output is correct |
| 68 | Correct | 54 ms | 97108 KB | Output is correct |
| 69 | Correct | 62 ms | 93588 KB | Output is correct |
| 70 | Correct | 56 ms | 101360 KB | Output is correct |
| 71 | Correct | 61 ms | 91920 KB | Output is correct |
| 72 | Correct | 21 ms | 42320 KB | Output is correct |
| 73 | Correct | 2 ms | 3028 KB | Output is correct |