# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
130276858 |
Practice:
Czhgugugu |
311B
- 10
|
C++17 (GCC 9-64)
|
Accepted
|
202 ms
|
9720 KB
|
2021-09-29 17:42:42 |
2021-09-29 17:42:43 |
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pin;
#ifndef ONLINE_JUDGE
bool MEMORY_ST;
#endif
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const ll P = 998244353LL;
int n, m, qn, mx, d[N], sd[N], h[N], q[N];
ll a[N], b[N], sum[N], f[2][N];
namespace Fread {
const int L = 1 << 15;
char buffer[L], *S, *T;
inline char Getchar() {
if(S == T) {
T = (S = buffer) + fread(buffer, 1, L, stdin);
if(S == T) return EOF;
}
return *S++;
}
template <class T>
inline void read(T &X) {
char ch; T op = 1;
for(ch = Getchar(); ch > '9' || ch < '0'; ch = Getchar())
if(ch == '-') op = -1;
for(X = 0; ch >= '0' && ch <= '9'; ch = Getchar())
X = (X << 1) + (X << 3) + ch - '0';
X *= op;
}
} using Fread::read;
inline ll yi(int cur, int i) {
return f[cur][i] + sum[i];
}
inline ll xi(int i) {
return i;
}
inline db slope(int c, int i, int j) {
return 1.0 * (yi(c, i) - yi(c, j)) / (xi(i) - xi(j));
}
#ifndef ONLINE_JUDGE
bool MEMORY_ED;
#endif
int main() {
#ifndef ONLINE_JUDGE
freopen("sample.in", "r", stdin);
clock_t st_clock = clock();
#endif
read(n), read(m), read(qn);
for (int i = 2; i <= n; i++) {
read(d[i]);
sd[i] = sd[i - 1] + d[i];
}
for (int i = 1; i <= m; i++) {
read(h[i]), read(a[i]);
b[i] = a[i] - 1LL * sd[h[i]];
}
sort(b + 1, b + 1 + m);
for (int i = 1; i <= m; i++) sum[i] = sum[i - 1] + b[i];
for (int i = 1; i <= qn; i++) {
int cur = i & 1, pre = cur ^ 1;
if (i == 1) {
for (int j = 0; j <= m; j++) f[cur][j] = 1LL * j * b[j] - sum[j];
continue;
}
f[cur][0] = 0;
int l = 1, r = 0;
q[++r] = 0;
for (int j = 1; j <= m; j++) {
for (; l < r && slope(pre, q[l], q[l + 1]) < b[j]; ++l);
f[cur][j] = f[pre][q[l]] + 1LL * (j - q[l]) * b[j] - sum[j] + sum[q[l]];
for (; l < r && slope(pre, q[r - 1], q[r]) > slope(pre, q[r], j); --r);
q[++r] = j;
}
}
printf("%lld\n", f[qn & 1][m]);
#ifndef ONLINE_JUDGE
clock_t ed_clock = clock();
printf("time = %f ms\n", (double)(ed_clock - st_clock) / CLOCKS_PER_SEC * 1000);
printf("memory = %.2f MB\n", (&MEMORY_ED - &MEMORY_ST) / 1024.0 / 1024.0);
#endif
return 0;
}
Click to see test details