Submission #1168472

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1168472	2025-03-17 10:49:01	yellowtoad	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	147 ms	4292 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 <iostream>
#define f first
#define s second
using namespace std;
int n, a[410], dp[410][410][3], tmp[410][410][3], ps[3][410], b[3][410], cnt[3]; // R, G
string s;
int sum(int x, int y, int z, int id) {
  pair<int,int> i, j, k;
  int res = 0;
  if (id == 0) i = {b[0][x],0}, j = min(make_pair(b[1][y],1),make_pair(b[2][z],2)), k = max(make_pair(b[1][y],1),make_pair(b[2][z],2));
  else if (id == 1) i = {b[1][y],1}, j = min(make_pair(b[0][x],0),make_pair(b[2][z],2)), k = max(make_pair(b[0][x],0),make_pair(b[2][z],2));
  else i = {b[2][z],2}, j = min(make_pair(b[0][x],0),make_pair(b[1][y],1)), k = max(make_pair(b[0][x],0),make_pair(b[1][y],1));
  if (i > k) res += i.f-k.f-ps[i.s][i.f]+ps[i.s][k.f];
  if (i > j) res += ps[j.s][min(i.f,k.f)]-ps[j.s][j.f];
  return res;
}
int main() {
  cin >> n >> s;
  for (int i = 1; i <= n; i++) {
    if (s[i-1] == 'R') a[i] = 0;
    else if (s[i-1] == 'G') a[i] = 1;
    else a[i] = 2;
    b[a[i]][++cnt[a[i]]] = i;
    for (int j = 0; j <= 2; j++) ps[j][i] = ps[j][i-1];
    ps[a[i]][i]++;
  }
  for (int j = 0; j <= n; j++) for (int k = 0; k <= n; k++) for (int l = 0; l <= 2; l++) dp[j][k][l] = 1e9;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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