Submission #147157

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
147157	2019-08-28 06:17:52	jh05013	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	219 ms	163072 KiB

joi2019_ho_t3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dbgv(V) for(auto x:V)cout<<x<<' ';cout<<endl;
#define FOR(a,n) for(int a=0;a<n;a++)
void OJize(){cin.tie(NULL); ios_base::sync_with_stdio(false);}
#define ZZ 401
#define INF 999999
int dp[ZZ][ZZ][ZZ][3];
int acc[3][ZZ];
// (r,g,y) counts, last R/G/B ... +1
vector<int> R, G, Y;
void upd(int r, int g, int y, int prev, int cur){
    // Where is the new vegetable?
    int pos=0, nr=r, ng=g, ny=y;
    if(cur == 0)      pos = R[r], nr++;
    else if(cur == 1) pos = G[g], ng++;
    else              pos = Y[y], ny++;
    // How much was it pushed to the right?
    int rig=0;
    if(cur != 0) rig+= max(0, r-acc[0][pos]);
    if(cur != 1) rig+= max(0, g-acc[1][pos]);
    if(cur != 2) rig+= max(0, y-acc[2][pos]);
    // Where is the desired position?
    int goal = r+g+y;
    int nv = dp[r][g][y][prev] + pos+rig-goal;
    dp[nr][ng][ny][cur] = min(dp[nr][ng][ny][cur], nv);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25