【APCS】2024年6月題解

#include <iostream>
using namespace std;

int main(){
    int n, now = 1, ans = 1;
    cin >> n;
    int a[n];
    for(int i=0; i<n; i++) cin >> a[i];
    for(int i=1; i<n; i++){
        now = (a[i] - a[i-1] > 0) ? 1 : now + 1;
        ans = max(ans, now);
    }
    cout << ans;
}

#include <iostream>
#include <cstring>
using namespace std;

int main(){
    int H, W, N, r, c, t, x;
    cin >> H >> W >> N;
    int a[H][W];
    memset(a, 0, sizeof(a));
    while(N--){
        cin >> r >> c >> t >> x;
        for(int i=0; i<H; i++){
            for(int j=0; j<W; j++){
                if(abs(i-r) + abs(j-c) <= t){
                    a[i][j] += x;
                }
            }
        }
    }
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            cout << a[i][j] << ' ';
        }
        cout << '\n';
    }
}

#include <iostream>
#include <vector>
#include <set>
using namespace std;

string dic;
vector<string> outputs;

void generate(string s, int L){
    if(L == 0) {outputs.push_back(s); return;}
    for(char c : dic) generate(s + c, L - 1);
}

int main() {
    int L; string S;
    cin >> dic >> L >> S;
    generate("", L);
    set<string> substrings;
    for(int i=0; i < S.size()-L+1; i++)
        substrings.insert(S.substr(i, L));
    for(string s : outputs){
        if(!substrings.count(s)){
            cout << s << '\n';
            return 0;
        }
    }
}

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n, k, x, totalSum = 0, diff = 0;
    cin >> n >> k;
    unordered_map<int, vector<int>> prefix_sum;
    for(int i=0; i<n; i++){
        cin >> x;
        totalSum += x;
        diff += (x % 2) ? 1 : -1;
        prefix_sum[diff].push_back(totalSum);
    }
    int retainedSum = totalSum;
    for(auto [current_diff, sums] : prefix_sum){
        if(!prefix_sum.count(current_diff + diff)) continue;
        vector<int> v = prefix_sum[current_diff + diff];
        for(int sum : sums){
            auto it = lower_bound(v.begin(), v.end(), sum + max(0, totalSum - k));
            if(it != v.end()) retainedSum = min(retainedSum, *it - sum);
        }
    }
    cout << totalSum - retainedSum;
}