oj.uz

답안 #955470

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
955470 2024-03-30T13:59:47 Z AlperenT Homecoming (BOI18_homecoming) C++17
100 / 100
 94 ms 55724 KB 
#include <bits/stdc++.h>
#include "homecoming.h"
 
using namespace std;

long long first_forced(int n, int k, int *a, int *b){
    long long mx, cur, cost, nxtcost;
    
    cost = accumulate(b, b + k, 0ll);
    
    mx = cur = a[0] - cost;
    
    for(int i = 1; i < n; i++){
        cost -= b[i - 1];
        nxtcost = i + k - 1 < n ? b[i + k - 1] : 0;
        
        cur = max(cur + a[i] - nxtcost, mx + a[i] - (cost + nxtcost));
        
        mx = max(mx, cur);
        cost += nxtcost;
    }
    
    return mx;
}

long long first_not_forced(int n, int k, int *a, int *b){
    long long mx, cur, cost, nxtcost;
    
    cost = accumulate(b, b + k, 0ll);
    
    mx = max(0ll, a[0] - cost);
    cur = a[0] - cost;
    
    for(int i = 1; i < n; i++){
        cost -= b[i - 1];
        nxtcost = i + k - 1 < n ? b[i + k - 1] : b[i + k - 1 - n];
        
        cur = max(cur + a[i] - nxtcost, mx + a[i] - (cost + nxtcost));
        
        mx = max(mx, cur);
        cost += nxtcost;
    }
    
    return mx;
}
 
long long solve(int n, int k, int *a, int *b){
	return max(first_forced(n, k, a, b), first_not_forced(n, k, a, b));
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 13716 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 94 ms 55724 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 6 ms 2592 KB Output is correct

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 25 ms 13716 KB Output is correct
12 Correct 2 ms 856 KB Output is correct
13 Correct 94 ms 55724 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 6 ms 2592 KB Output is correct
16 Correct 94 ms 55444 KB Output is correct
17 Correct 54 ms 20144 KB Output is correct
18 Correct 91 ms 38480 KB Output is correct
19 Correct 67 ms 35416 KB Output is correct
20 Correct 76 ms 38660 KB Output is correct
21 Correct 75 ms 32984 KB Output is correct