JOI_Yosen

JOI予選問題のソースコード

q1.cpp

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;
    int ans = a+b+c+d+e+f-min(a,min(b,min(c,d)))-min(e,f);

    cout << ans << endl;
}

q2.cpp

#include<iostream>

using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    int a[n] = {};
    for(int i=0; i<n;++i){
        cin >> a[i];
    }
    for(int k=1; k<=m; ++k){
        for(int i=0; i<n-1; ++i){
            if(a[i]%k > a[i+1]%k){
                int tmp = a[i];
                a[i] = a[i+1];
                a[i+1] = tmp;
            }
        }
    }
    for(int i=0;i<n;++i){
        cout << a[i] << endl;
    }
}

q3.cpp

#include<iostream>
#include<algorithm>
#define INF 1e9
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    int cost_w[n], cost_b[n], cost_r[n];
    for (int i=0; i<n; ++i){
        cost_w[i] = m;
        cost_b[i] = m;
        cost_r[i] = m;
        char str[m+1];
        cin >> str;
        for(int j=0; j<m; ++j){
            if(str[j] == 'W') --cost_w[i];
            if(str[j] == 'B') --cost_b[i];
            if(str[j] == 'R') --cost_r[i];
        }
    }
    cost_w[n-2] = cost_w[n-1] = cost_b[n-1] = cost_b[0] = cost_r[0] = cost_r[1] = INF;
    int total_cost_w[n]={}, total_cost_b[n], total_cost_r[n];
    total_cost_w[0] = cost_w[0];
    total_cost_b[0] = cost_b[0];
    total_cost_r[0] = cost_r[0];
    for(int i=1; i<n; ++i){
        total_cost_w[i] = total_cost_w[i-1] + cost_w[i];
        total_cost_b[i] = min(total_cost_b[i-1], total_cost_w[i-1]) + cost_b[i];
        total_cost_r[i] = min(total_cost_r[i-1], total_cost_b[i-1]) + cost_r[i];
    }
    cout << total_cost_r[n-1] << endl;
}

q4.cpp

#include<iostream>
#include<vector>
#include<cmath>
#define INF 9e18

typedef long long int ll;
using namespace std;
int main(){
    ll n, t, q;
    cin >> n >> t >> q;
    ll stop_index[n] = {}, start_point[n] = {}, direction[n] = {};

    vector<ll> node;
    node.push_back(-INF);

    bool dir_was_1 = false;
    ll s_ind = 0;
    for(int i=0; i<n; ++i){
        cin >> start_point[i] >> direction[i];
        if(dir_was_1 && direction[i] == 2)
        {
            node.push_back((start_point[i-1]+start_point[i])/2);
            dir_was_1 = false;
        }
        else if(!dir_was_1 && direction[i] == 1)
        {
            dir_was_1 = true;
            ++s_ind;
        }
        stop_index[i] = s_ind;
    }
    if(dir_was_1) node.push_back(INF);

    ll qi;
    for(int i=0; i<q; ++i){
        cin >> qi;
        --qi;
        ll sp = start_point[qi], si = stop_index[qi];
        ll dist = abs(sp - node[si]);
        //cout << "dist:" << dist << ", t:" << t << ", node:" << node[si] << endl;
        if(dist <= t){
            cout << node[si] << endl;
        }
        else if(direction[qi] == 1){
            cout << sp + t << endl;
        }
        else{
            cout << sp - t << endl;
        }
    }
}

q5.cpp

#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#include<queue>
#define INF 1e12
#define INFF 1e18
using namespace std;

typedef long long int ll;
typedef pair<int,int> Path;
typedef pair<ll,int> cot;
int main(){
    int n, m, k, s, p, q;
    cin >> n >> m >> k >> s;
    int dang[n+1] = {};
    ll cost[n+1] = {};
    cin >> p >> q;
    queue<int> que;
    for (int i=0; i<k; ++i){
        int ci;
        cin >> ci;
        dang[ci] = s+1;
        cost[ci] = INF;
        que.push(ci);
    }
    vector<Path> path, rpath;
    for(int j=0; j<m; ++j){
        int a, b;
        cin >> a >> b;
        path.push_back(Path(a,b));
        rpath.push_back(Path(b,a));
    }
    sort(path.begin(), path.end());
    sort(rpath.begin(), rpath.end());
    ll total_cost[n] = {};
    for(int i=1; i<=n; ++i){
        cost[i] = p;
        total_cost[i] = INFF;
    }
    cost[1] = 0;
    cost[n] = 0;
    int d_point;
    while(!que.empty()){
        int tmp = que.front();
        que.pop();
        d_point = dang[tmp];
        vector<Path>::iterator it = lower_bound(path.begin(), path.end(), Path(tmp,0));
        vector<Path>::iterator it_end = lower_bound(path.begin(), path.end(), Path(tmp+1,0));
        while(it != it_end){
            int d = (*it).second;
            if(dang[d] < d_point-1){
                dang[d] = d_point-1;
                cost[d] = q;
                if(dang[d] > 1) que.push(d);
            }
            ++it;
        }
        vector<Path>::iterator rit = lower_bound(rpath.begin(), rpath.end(), Path(tmp,0));
        vector<Path>::iterator rit_end = lower_bound(rpath.begin(), rpath.end(), Path(tmp+1,0));
        while(rit != rit_end){
            int d = (*rit).second;
            if(dang[d] < d_point-1){
                dang[d] = d_point-1;
                cost[d] = q;
                if(dang[d] > 1) que.push(d);
            }
            ++rit;
        }
    }

    priority_queue<cot, vector<cot>, greater<cot> > cots;
    cots.push(cot(0,1));
    while(!cots.empty()){
    //cout << "hoge" << endl;
        cot c = cots.top();
        cots.pop();
        int tmp = c.second;
        if(total_cost[c.second] > c.first){
            total_cost[c.second] = c.first;
            vector<Path>::iterator it = lower_bound(path.begin(), path.end(), Path(tmp,0));
            vector<Path>::iterator it_end = lower_bound(path.begin(), path.end(), Path(tmp+1,0));
            while(it != it_end){
                int d = (*it).second;
                cots.push(cot(total_cost[tmp] + cost[d], d));
                ++it;
            }
        }
    }

    cout << total_cost[n] << endl;
}