oj.uz

답안 #498474

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
498474 2021-12-25T09:27:41 Z Yuisuyuno Palembang Bridges (APIO15_bridge) C++14
100 / 100
 216 ms 14360 KB 
//Nguyen Huu Hoang Minh
#include <bits/stdc++.h>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define reset(x) memset(x, 0,sizeof(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define N 100005
#define remain(x) if (x > MOD) x -= MOD
#define ii pair<int, int>
#define iiii pair< ii , ii >
#define viiii vector< iiii >
#define vi vector<int>
#define vii vector< ii >
#define bit(x, i) (((x) >> (i)) & 1)
#define Task "test"
#define int long long

using namespace std;

typedef long double ld;
const int inf = 1e10;
const int minf = -1e10;

int n, k;
struct ppl{
    int s, t;
    bool operator < (const ppl &a) const{
        return s+t < a.s + a.t;
    }
};
vector<ppl> Q;
int same_side = 0;
int pref[N];
multiset<int> low, high;
int sumr, suml;

void add(int x){
    int med = (low.size() ? *low.rbegin() : 1e15);
    if (x <= med){
        low.insert(x); suml+=x;
    }
    else high.insert(x), sumr+=x;
    if (low.size() > high.size()+1){
        int tmp = *low.rbegin();
        suml -= tmp;
        high.insert(tmp);
        sumr += tmp;
        low.erase(low.find(tmp));
    }
    else if (low.size() < high.size()){
        int tmp = *high.begin();
        sumr -= tmp;
        suml += tmp;
        low.insert(tmp);
        high.erase(high.find(tmp));
    }
}

void readfile()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    if (fopen(Task".inp","r"))
    {
        freopen(Task".inp","r",stdin);
        //freopen(Task".out","w",stdout);
    }
    cin >> k >> n;
    for(int i=1; i<=n; i++){
        char a, b;
        int x, y;
        cin >> a >> x >> b >> y;
        if (a==b) same_side += abs(x-y);
        else{
            Q.pb({x,y});
        }
    }
    sort(all(Q));
}

void proc()
{
    n = Q.size();
    same_side += n;
    for(int i=0; i<Q.size(); i++){
        add(Q[i].s);
        add(Q[i].t);
        pref[i] = sumr - suml;
    }
    int ans = pref[n-1];
    if (k==2){
        suml = 0; sumr = 0; low.clear(); high.clear();
        for(int i=n-1; i>=0; i--){
            add(Q[i].s);
            add(Q[i].t);
            ans = min(ans,sumr - suml + pref[i-1]);
        }
    }
    cout << same_side + ans;
}

signed main()
{
    readfile();
    proc();
    return 0;
}

Compilation message

bridge.cpp: In function 'void proc()':
bridge.cpp:88:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<ppl>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i=0; i<Q.size(); i++){
      |                  ~^~~~~~~~~
bridge.cpp: In function 'void readfile()':
bridge.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 80 ms 12044 KB Output is correct
13 Correct 153 ms 12048 KB Output is correct
14 Correct 95 ms 10816 KB Output is correct
15 Correct 56 ms 7240 KB Output is correct
16 Correct 73 ms 12040 KB Output is correct
17 Correct 79 ms 11984 KB Output is correct
18 Correct 72 ms 12024 KB Output is correct
19 Correct 94 ms 12004 KB Output is correct
20 Correct 86 ms 11956 KB Output is correct
21 Correct 80 ms 11960 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 324 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 320 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 1 ms 472 KB Output is correct

Subtask #5
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 324 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 436 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 288 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 139 ms 12796 KB Output is correct
26 Correct 209 ms 12992 KB Output is correct
27 Correct 216 ms 13752 KB Output is correct
28 Correct 212 ms 14268 KB Output is correct
29 Correct 214 ms 14348 KB Output is correct
30 Correct 123 ms 7696 KB Output is correct
31 Correct 121 ms 13700 KB Output is correct
32 Correct 160 ms 14360 KB Output is correct
33 Correct 111 ms 13872 KB Output is correct
34 Correct 135 ms 14352 KB Output is correct
35 Correct 189 ms 13944 KB Output is correct
36 Correct 135 ms 14128 KB Output is correct
37 Correct 145 ms 12796 KB Output is correct