A. Curriculum Vitae

The problem requires finding the longest subsequence where digit 1 is never followed by digit 0. This is equivalent to finding the longest non-decreasing subsequence in a binary sequence. An alternative approach uses prefix sums to count zeros and suffix sums to count ones.

#include  <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    
    vector<int> zeroPrefix(n + 1, 0);
    vector<int> oneSuffix(n + 2, 0);
    
    for(int i = 0; i < n; i++){
        zeroPrefix[i + 1] = zeroPrefix[i] + (arr[i] == 0 ? 1 : 0);
    }
    for(int i = n - 1; i >= 0; i--){
        oneSuffix[i] = oneSuffix[i + 1] + (arr[i] == 1 ? 1 : 0);
    }
    
    int result = 0;
    for(int i = 0; i <= n; i++){
        int zeros = zeroPrefix[i];
        int ones = oneSuffix[i];
        result = max(result, zeros + ones);
    }
    cout << result << endl;
    return 0;
}

Alternatively, a dynamic programming approach can solve this in O(n²):

#include  <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> data(n);
    for(int i = 0; i < n; i++) cin >> data[i];
    
    vector<int> dp(n, 1);
    int maxLen = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            if(data[i] >= data[j]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    cout << maxLen << endl;
    return 0;
}

B. Math Show

With small constraints, a brute force greedy solution works effectively. The key insight is to first determine how many complete problem sets can be finished, then greedily assign remaining problems to maximize score.

#include  <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k, M;
    cin >> n >> k >> M;
    vector<int> problems(k + 1);
    int totalTime = 0;
    for(int i = 1; i <= k; i++){
        cin >> problems[i];
        totalTime += problems[i];
    }
    sort(problems.begin() + 1, problems.end());
    
    int bestScore = 0;
    for(int completed = 0; completed <= n; completed++){
        int timeUsed = totalTime * completed;
        int currentScore = completed * k + completed;
        
        if(timeUsed > M) break;
        
        int remaining = n - completed;
        for(int idx = 1; idx <= k && timeUsed < M; idx++){
            int assignments = remaining;
            while(assignments > 0 && timeUsed < M){
                timeUsed += problems[idx];
                if(timeUsed <= M){
                    currentScore++;
                }
                assignments--;
            }
        }
        bestScore = max(bestScore, currentScore);
    }
    cout << bestScore << endl;
    return 0;
}

C. Four Segments

The goal is to find indices i, j, k that maximize:

$$\text{sum}(0, i) - \text{sum}(i, j) + \text{sum}(j, k) - \text{sum}(k, n)$$

where sum(a, b) represents the prefix sum difference. Notice that when j is fixed, the expression splits into two independent parts: the first depends only on i, and the second depends only on k. This allows us to compute optimal i and k for each j independently.

#include  <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> arr(n + 1);
    for(int i = 1; i <= n; i++) cin >> arr[i];
    
    vector<int> prefix(n + 1, 0);
    for(int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + arr[i];
    
    int answer = LLONG_MIN;
    int bestI = 0, bestJ = 0, bestK = 0;
    
    for(int j = 0; j <= n; j++){
        int leftBest = LLONG_MIN;
        int leftIdx = 0;
        for(int i = 0; i <= j; i++){
            int value = prefix[i] - (prefix[j] - prefix[i]);
            if(value > leftBest){
                leftBest = value;
                leftIdx = i;
            }
        }
        
        int rightBest = LLONG_MIN;
        int rightIdx = 0;
        for(int k = j; k <= n; k++){
            int value = prefix[k] - prefix[j] - (prefix[n] - prefix[k]);
            if(value > rightBest){
                rightBest = value;
                rightIdx = k;
            }
        }
        
        int total = leftBest + rightBest;
        if(total > answer){
            answer = total;
            bestI = leftIdx;
            bestJ = j;
            bestK = rightIdx;
        }
    }
    cout << bestI << ' ' << bestJ << ' ' << bestK << endl;
    return 0;
}

D. Monitor

Given q defective pixels with coordinates and timestamps, determine earliest moment when these defects form a k×k square. If no such configuration exists, output -1.

The solution uses binary search on time, combined with 2D prefix sums to efficiently check whether any k×k square is completely filled.

#include  <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

struct Defect {
    int x, y, time;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int rows, cols, k, q;
    cin >> rows >> cols >> k >> q;
    
    vector<Defect> defects(q + 1);
    for(int i = 1; i <= q; i++){
        cin >> defects[i].x >> defects[i].y >> defects[i].time;
    }
    
    sort(defects.begin() + 1, defects.end(), [](Defect a, Defect b){
        return a.time < b.time;
    });
    
    auto validate = [&](vector<vector<int>>& grid) -> bool {
        for(int i = k; i <= rows; i++){
            for(int j = k; j <= cols; j++){
                int count = grid[i][j] - grid[i - k][j] - grid[i][j - k] + grid[i - k][j - k];
                if(count == k * k) return true;
            }
        }
        return false;
    };
    
    int left = 1, right = q;
    while(left <= right){
        int mid = (left + right) >> 1;
        
        vector<vector<int>> status(rows + 1, vector<int>(cols + 1, 0));
        for(int i = 1; i <= mid; i++){
            status[defects[i].x][defects[i].y] = 1;
        }
        
        for(int i = 1; i <= rows; i++){
            for(int j = 1; j <= cols; j++){
                status[i][j] += status[i - 1][j] + status[i][j - 1] - status[i - 1][j - 1];
            }
        }
        
        if(validate(status)){
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    cout << (left > q ? -1 : defects[left].time) << endl;
    return 0;
}

The binary search finds the minimum threshold where the condition becomes satisfied. If the search exhausts all q defects without finding a valid square, the output is -1.