Submission #463532

#	Time	Username	Problem	Language	Result	Execution time	Memory
463532		Mounir	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	125 ms	15484 KiB

ho_t1

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define all(x) x.begin(), x.end()
#define pb push_back
#define pii pair<int, int>
#define deb first
#define fin second
#define int long long
using namespace std;
 
signed main(){ 
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);
 
      int nVals; cin >> nVals;
      vector<pii> avant(nVals + 1);
      for (int i  =0; i <= nVals; ++i){
            cin >> avant[i].first;
            avant[i].second = i;
      }

      vector<int> apres(nVals);
      for (int& e : apres)
            cin >> e;

      sort(all(avant));
      sort(all(apres));

      vector<int> res(nVals + 1);
      int maxi[2][nVals + 1];
      maxi[0][0] = max(avant[0].first - apres[0], 0ll);
      for (int i = 1; i < nVals; ++i)
            maxi[0][i] = max(maxi[0][i - 1], avant[i].first - apres[i]);
      maxi[1][nVals] = max(avant[nVals].first - apres[nVals - 1], 0ll);
      for (int i = nVals - 1; i > 0; --i)
            maxi[1][i] = max(maxi[1][i + 1], avant[i].first - apres[i - 1]);

      for (int i = 0; i <= nVals; ++i){
            res[avant[i].second] = 0;
            if (i != 0) chmax(res[avant[i].second], maxi[0][i - 1]);
            if (i != nVals) chmax(res[avant[i].second], maxi[1][i + 1]);
      }

      for (int e : res)
            cout << e << " ";
      cout << endl;
      return 0;
 
}

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91