Submission #491207

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
491207	2021-11-30 18:08:12	macktvz	Nafta (COI15_nafta)	C++17	34 / 100	1000 ms	141880 KiB

nafta

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;
using ll = long long;
// the value of k that minimizes dp[p-1][k-1] + (p[i]-p[k-1])^2
// is <= k that minimizes dp[p-1][k-1] + (p[i+1]-p[k-1])^2
const int R = 2e3+1;
bool vis1[R][R];
bool vis2[R][R];
int id[R][R];
int grid[R][R];
int n,m;
int oil[R*R];
vector<int> dp_cur(R,0),dp_last(R,0);
vector<int> Li(R*R,R);
vector<int> Ri(R*R,-1);
int poil[R];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
vector<vector<int>> bad(R,vector<int>(R,0));
int bit[R*R];
int ans[R];
void update(int i, int val) {
  for (; i <= m; i+=i&(-i)) {
    bit[i]+=val;
  }
}
int qry(int i) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 66