NOI.AC
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #214174 | #2031. a | nodgd | 0 | 0ms | 1260kb | C++11 | 1.1kb | 2024-11-15 21:34:14 | 2024-11-15 23:28:23 |
answer
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 300 + 5;
const int INF32 = 1e9;
int N, K;
pair<int,int> a[MAX_N];
int A, av[MAX_N << 1];
vector<int> al[MAX_N << 1];
int f[MAX_N << 1];
int main() {
scanf("%d%d", &N, &K);
for (int i = 1; i <= N; i ++) {
int l, r;
scanf("%d%d", &l, &r);
av[++ A] = l;
av[++ A] = r;
a[i] = make_pair(l, r);
}
sort(av + 1, av + 1 + A);
A = unique(av + 1, av + 1 + A) - av - 1;
for (int i = 1; i <= N; i ++) {
int l = lower_bound(av + 1, av + 1 + A, a[i].first) - av;
int r = lower_bound(av + 1, av + 1 + A, a[i].second) - av;
a[i] = make_pair(l, r);
al[r].push_back(l);
}
for (int k = 1; k <= K; k ++) {
for (int i = A; i >= 1; i --) {
for (int l: al[i]) {
f[i] = max(f[i], f[l] + i - l);
}
}
for (int i = 1; i <= A; i ++) {
f[i] = max(f[i], f[i - 1]);
}
}
printf("%d\n", f[A]);
return 0;
}
Details
小提示：点击横条可展开更详细的信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 1256kb
input:
20 8 941374267 958239792 636546050 949277063 30572593 458894768 377940690 585510776 595907552 909524...
output:
37
result:
wrong answer 1st lines differ - expected: '982023824', found: '37'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 1256kb
input:
20 15 76365869 433406218 633171333 786737074 131600137 929106040 44288699 688307921 419471992 769278...
output:
35
result:
wrong answer 1st lines differ - expected: '923804666', found: '35'
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 1260kb
input:
20 2 358841118 908572644 771680732 777280263 232627681 399317312 146158799 355582975 95552785 629032...
output:
35
result:
wrong answer 1st lines differ - expected: '898648766', found: '35'
Test #4:
score: 0
Runtime Error
input:
5000 49 383739070 641316367 609140743 773905546 333655225 869528584 456526030 666877251 488787058 91...
output:
result:
Test #5:
score: 0
Runtime Error
input:
5000 56 6389143 923791616 594084401 918014476 192256209 434682769 125655174 766893261 348541120 7426...
output:
result:
Test #6:
score: 0
Runtime Error
input:
5000 63 206266865 481555569 431544412 914639759 535710313 662467481 77260492 436949450 208295182 418...
output:
result:
Test #7:
score: 0
Runtime Error
input:
100000 95 31394575 31395303 35035434 35036166 64896609 64897277 10992021 10992677 17899328 17900254 ...
output:
result:
Test #8:
score: 0
Runtime Error
input:
100000 83 233039267 233039367 916657359 916657459 864715109 864715209 936842396 936842496 562959930 ...
output:
result:
Test #9:
score: 0
Runtime Error
input:
100000 90 816642137 816642237 185449925 185450025 619425312 619425412 335954840 335954940 14523568 1...
output:
result:
Test #10:
score: 0
Runtime Error
input:
100000 85 932471751 932471851 591128329 591128429 632579047 632579147 902529780 902529880 377540930 ...
