codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2051.md (6658B)


      1 Source: https://codeforces.com/blog/entry/137623
      2 
      3 [2051A - Preparing for the Olympiad](/contest/2051/problem/A "Codeforces Round 995 (Div. 3)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Neon)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15  
     16 using namespace std;
     17 
     18 int main() {
     19   int t;
     20   cin >> t;
     21   while (t--) {
     22     int n;
     23     cin >> n;
     24     vector<int> a(n), b(n);
     25     for (auto &x : a) cin >> x;
     26     for (auto &x : b) cin >> x;
     27     int ans = a[n - 1];
     28     for (int i = 0; i < n - 1; ++i)
     29       ans += max(0, a[i] - b[i + 1]);
     30     cout << ans << '\n';
     31   }
     32 }
     33 ```
     34 
     35 [2051B - Journey](/contest/2051/problem/B "Codeforces Round 995 (Div. 3)")
     36 
     37 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution (BledDest)**
     44 
     45 ```
     46 t = int(input())
     47 for i in range(t):
     48     n, a, b, c = map(int, input().split())
     49     sum = a + b + c
     50     d = n // sum * 3
     51     if n % sum == 0:
     52         print(d)
     53     elif n % sum <= a:
     54         print(d + 1)
     55     elif n % sum <= a + b:
     56         print(d + 2)
     57     else:
     58         print(d + 3)
     59 ```
     60 
     61 [2051C - Preparing for the Exam](/contest/2051/problem/C "Codeforces Round 995 (Div. 3)")
     62 
     63 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     64 
     65 **Tutorial**
     66 
     67 Tutorial is loading...
     68 
     69 **Solution (BledDest)**
     70 
     71 ```
     72 for _ in range(int(input())):
     73     n, m, k = map(int, input().split())
     74     a = list(map(int, input().split()))
     75     q = list(map(int, input().split()))
     76     used = [False for i in range(n + 1)]
     77     for i in q:
     78         used[i] = True
     79     l = len(q)
     80     for i in range(m):
     81         if l == n or (l == n-1 and not used[a[i]]):
     82             print(1, end='')
     83         else:
     84             print(0, end='')
     85     print()
     86 ```
     87 
     88 [2051D - Counting Pairs](/contest/2051/problem/D "Codeforces Round 995 (Div. 3)")
     89 
     90 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
     91 
     92 **Tutorial**
     93 
     94 Tutorial is loading...
     95 
     96 **Solution (BledDest)**
     97 
     98 ```
     99 def calcLessThanX(a, x):
    100     n = len(a)
    101     s = sum(a)
    102     j = 0
    103     ans = 0
    104 
    105     for i in range(n-1, -1, -1):
    106         while j < n and s - a[i] - a[j] >= x:
    107             j += 1
    108         ans += (n - j)
    109 
    110     for i in range(n):
    111         if s - a[i] - a[i] < x:
    112             ans -= 1
    113     
    114     return ans // 2
    115 
    116 for _ in range(int(input())):
    117     n, x, y = map(int, input().split())
    118     a = list(map(int, input().split()))
    119     
    120     a = sorted(a)
    121     print(calcLessThanX(a, y+1) - calcLessThanX(a, x))
    122 ```
    123 
    124 [2051E - Best Price](/contest/2051/problem/E "Codeforces Round 995 (Div. 3)")
    125 
    126 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    127 
    128 **Tutorial**
    129 
    130 Tutorial is loading...
    131 
    132 **Solution (Neon)**
    133 
    134 ```
    135 #include <bits/stdc++.h>
    136  
    137 using namespace std;
    138 
    139 int main() {
    140   ios::sync_with_stdio(false); cin.tie(0);
    141   int t;
    142   cin >> t;
    143   while (t--) {
    144     int n, k;
    145     cin >> n >> k;
    146     vector<int> a(n), b(n);
    147     for (auto &x : a) cin >> x;
    148     for (auto &x : b) cin >> x;
    149     vector<pair<int, int>> ev;
    150     for (int i = 0; i < n; ++i) {
    151       ev.emplace_back(a[i], 1);
    152       ev.emplace_back(b[i], 2);
    153     }
    154     sort(ev.begin(), ev.end());
    155     long long ans = 0;
    156     int cnt = n, bad = 0;
    157     for (int i = 0; i < 2 * n;) {
    158       auto [x, y] = ev[i];
    159       if (bad <= k) ans = max(ans, x * 1LL * cnt);
    160       while (i < 2 * n && ev[i].first == x) {
    161         bad += (ev[i].second == 1);
    162         bad -= (ev[i].second == 2);
    163         cnt -= (ev[i].second == 2);
    164         ++i;
    165       }
    166     }
    167     cout << ans << '\n';
    168   }
    169 }
    170 ```
    171 
    172 [2051F - Joker](/contest/2051/problem/F "Codeforces Round 995 (Div. 3)")
    173 
    174 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    175 
    176 **Tutorial**
    177 
    178 Tutorial is loading...
    179 
    180 **Solution (Neon)**
    181 
    182 ```
    183 #include <bits/stdc++.h>
    184  
    185 using namespace std;
    186 
    187 int main() {
    188   int t;
    189   cin >> t;
    190   while (t--) {
    191     int n, m, q;
    192     cin >> n >> m >> q;
    193     vector<pair<int, int>> segs({{1, -q}, {m, m}, {n + q + 1, n}});
    194     while (q--) {
    195       int x;
    196       cin >> x;
    197       bool ins = false;
    198       for (auto& [l, r] : segs) {
    199         if (x < l) l = max(1, l - 1);
    200         else if (x > r) r = min(n, r + 1);
    201         else {
    202           ins = true;
    203           if (l == r) l = n + q, r = -q;
    204         }
    205       }
    206       if (ins) {
    207         segs[0] = {1, max(segs[0].second, 1)};
    208         segs[2] = {min(segs[2].first, n), n};
    209       }
    210       int lf = 0, rg = -1, ans = 0;
    211       for (auto [l, r] : segs) {
    212         if (l > r) continue;
    213         if (l > rg) {
    214           ans += max(0, rg - lf + 1);
    215           lf = l; rg = r;
    216         }
    217         rg = max(rg, r);
    218       }
    219       ans += max(0, rg - lf + 1);
    220       cout << ans << ' ';
    221      }
    222      cout << '\n';
    223   }
    224 }
    225 ```
    226 
    227 [2051G - Snakes](/contest/2051/problem/G "Codeforces Round 995 (Div. 3)")
    228 
    229 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    230 
    231 **Tutorial**
    232 
    233 Tutorial is loading...
    234 
    235 **Solution (adedalic)**
    236 
    237 ```
    238 #include<bits/stdc++.h>
    239 
    240 using namespace std;
    241 
    242 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    243 #define sz(a) int((a).size())
    244 
    245 const int INF = int(1e9);
    246 
    247 int n, q;
    248 vector<int> id, ch;
    249 
    250 bool read() {
    251     if (!(cin >> n >> q))
    252         return false;
    253     id.resize(q);
    254     ch.resize(q);
    255     fore (i, 0, q) {
    256         char c;
    257         cin >> id[i] >> c;
    258         id[i]--;
    259         ch[i] = c == '+' ? 1 : -1;
    260     }
    261     return true;
    262 }
    263 
    264 int getDist(int s, int t) {
    265     int pSum = 0, cMin = 0;
    266     fore (e, 0, q) {
    267         if (id[e] == t)
    268             pSum += ch[e] < 0;
    269         if (id[e] == s)
    270             pSum -= ch[e] > 0;
    271         cMin = min(cMin, pSum);
    272     }
    273     return -cMin + 1;
    274 }
    275 
    276 inline void solve() {
    277     vector<vector<int>> minDist(n, vector<int>(n, INF));
    278 
    279     fore (i, 0, n) fore (j, 0, n)
    280         minDist[i][j] = getDist(i, j);
    281 
    282     vector<int> len(n, 0);
    283     fore (e, 0, q)
    284         len[id[e]] += ch[e] > 0;
    285     
    286     vector< vector<int> > d(1 << n, vector<int>(n, INF));
    287     fore (i, 0, n)
    288         d[1 << i][i] = 1;
    289     
    290     fore (mask, 1, 1 << n) fore (lst, 0, n) {
    291         if (d[mask][lst] == INF)
    292             continue;
    293         fore (nxt, 0, n) {
    294             if ((mask >> nxt) & 1)
    295                 continue;
    296             int nmask = mask | (1 << nxt);
    297             d[nmask][nxt] = min(d[nmask][nxt], d[mask][lst] + minDist[lst][nxt]);
    298         }
    299     }
    300     int ans = INF;
    301     fore (lst, 0, n)
    302         ans = min(ans, d[(1 << n) - 1][lst] + len[lst]);
    303     cout << ans << endl;
    304 }
    305 
    306 int main() {
    307 #ifdef _DEBUG
    308     freopen("input.txt", "r", stdin);
    309     int tt = clock();
    310 #endif
    311     ios_base::sync_with_stdio(false);
    312 
    313     if(read()) {
    314         solve();
    315         
    316 #ifdef _DEBUG
    317         cerr << "TIME = " << clock() - tt << endl;
    318         tt = clock();
    319 #endif
    320     }
    321     return 0;
    322 }
    323 ```