This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vec vector
#define eb emplace_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
void read(vector<ll> &a){
for(ll &i : a) cin >> i;
}
void read(vector<int> &a){
for(int &i : a) cin >> i;
}int INF = 1e9;
int mod = 1e9+7;
long long fastpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
vector<int> pow2(25);
const int maxn = 1e6+6;
const int maxk = 10;
int dp[maxn];
int pref[maxn][maxk];
int check(int num){
// debug() << imie(num) imie(dp[num]);
if(dp[num] != -1){
return dp[num];
} else{
string s = to_string(num);
if(s.size() == 1){
return dp[num]=(s[0]-'0');
}
int nnum = 1;
for(int i = 0; i < s.size(); i++){
if(s[i] != '0'){
// debug() << imie(nnum) imie(s[i] - '0');
nnum = nnum * (s[i] - '0');
}
}
// for(char i : s){
// if(i != '0') num *= (i - '0');
// }
// debug() << imie(s) imie(nnum);
return dp[num] = check(nnum);
}
}
void test_case(int tnum){
int n;
cin >> n;
vector<pair<ll, ll>> a;
for(int i = 0; i < n; i++){
ll sz, p;
cin >> sz >> p;
a.pb({sz, p});
}
sort(a.begin(), a.end());
// debug() << imie(a);
int l, r;
l = r = 0;
vector<ll> pref(n+1);
pref[0] = 0;
for(int i = 1; i <= n; i++){
pref[i] = pref[i-1] + a[i-1].second;
}
ll ans = 0;
l = 0;
r = 0;
// debug() << imie(pos) imie(best);
while(r < n){
ll val = pref[r+1] - pref[l];
ll sub = a[r].first - a[l].first;
ans = max(ans, val-sub);
if(l != r && val - a[l].second - (a[r].first - a[l+1].first) > val-sub){
l++;
} else{
r++;
}
}
cout << ans << '\n';
}
int main(void){
cin.tie(0);
int t = 1;
// cin >>t;
for(int test = 1; test <= t; test++){
// cout << "Case #" << test << ": ";
test_case(test);
}
return 0;
}
Compilation message (stderr)
art.cpp: In function 'int check(int)':
art.cpp:74:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = 0; i < s.size(); i++){
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |