akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int mod = 1e9 + 7;

ll pw(ll a, ll b) {
    ll r = 1;
    for( ; b ; b >>= 1, a = a * a % mod) {
        if(b & 1) {
            r = r * a % mod;
        }
    }
    return r;
}

ll getinv(ll n) {
    return pw(n, mod - 2);
}

const int N = 2010;
char str[N][N];
int n, m;
int lef[N][N], rig[N][N];
int up[N][N], dn[N][N];

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1 ; i <= n ; ++ i) {
        scanf("%s", str[i] + 1);
    }
    for(int i = 1 ; i <= n ; ++ i) {
        for(int j = 1 ; j <= m ; ++ j) {
            if(str[i][j] == '.') {
                lef[i][j] = lef[i][j - 1] + 1;
                up[i][j] = up[i - 1][j] + 1;
            }
        }
    }
    for(int i = n ; i >= 1 ; -- i) {
        for(int j = m ; j >= 1 ; -- j) {
            if(str[i][j] == '.') {
                rig[i][j] = rig[i][j + 1] + 1;
                dn[i][j] = dn[i + 1][j] + 1;
            }
        }
    }
    int ans = 0;
    for(int i = 1 ; i <= n ; ++ i) {
        for(int j = 1 ; j <= m ; ++ j) {
            if(str[i][j] == '.') {
                ans = max(ans, up[i][j] + rig[i][j] + lef[i][j] + dn[i][j] - 3);
            }
        }
    }
    printf("%d\n", ans);
}


Measured memory_bytes: 67328
/**
 * @brief  : c++ code for AtCoder
 * @author : rk222
 * @created: 2019.05.10 13:52:46
 */

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<int, P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i, x) for (int i = 0; i < x; i++)
#define rep1(i, x) for (int i = 1; i <= x; i++)
#define rrep(i, x) for (int i = x - 1; i >= 0; i--)
#define rrep1(i, x) for (int i = x; i > 0; i--)
#define sor(v) sort(v.begin(), v.end())
#define rev(s) reverse(s.begin(), s.end())
#define lb(vec, a) lower_bound(vec.begin(), vec.end(), a)
#define ub(vec, a) upper_bound(vec.begin(), vec.end(), a)
#define uniq(vec) vec.erase(unique(vec.begin(), vec.end()), vec.end())
#define mp1(a, b, c) P1(a, P(b, c))

#define disp(x) cout << #x << ": " << x << endl
#define disp_vec(v)                                                                           \
    cout << #v << ":";                                                                        \
    rep(i, v.size()) cout << " " << v[i];                                                     \
    cout << endl

const int INF = 100000000;
const int M = 100000000;
const int dir_4[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int dir_8[8][2] = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};

// ===================### 素数取得 ###=================== //
// bool primeDp[100000];
// vector<int> getPrimes(int n) {
//     int u = n + 32;
//     double lu = log(u);
//     vector<int> ret((int)(u / lu + u / lu / lu * 1.5));

//     for (int i = 2; i <= n; i++)
//         primeDp[i] = true;
//     int sqn = sqrt(n);
//     for (int i = 2; i <= sqn; i++) {
//         if (!primeDp[i])
//             continue;
//         for (int j = i * i; j <= n; j += i)
//             primeDp[j] = false;
//     }
//     int idx = 0;
//     for (int i = 2; i <= n; i++) {
//         if (primeDp[i]) {
//             ret[idx] = i;
//             idx++;
//         }
//     }
//     return vector<int>(ret.begin(), ret.begin() + idx);
// }
/* ------------------------------------- */

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    int siz = min((int)sqrt(m), m / n);
    rep1(i_, siz) {
        if (m % i_ != 0)
            continue;
        int i = m / i_;
        int t = m / i;
        if (t >= n) {
            printf("%d\n", i);
            return 0;
        }
    }
    rrep1(i, siz) {
        if (m % i != 0)
            continue;
        int t = m / i;
        if (t >= n) {
            printf("%d\n", i);
            return 0;
        }
    }

    /* --------------------------------- */
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long

struct UnionFind {
  vector<int> data;

  UnionFind(int size) : data(size, -1) { }

  bool union_(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }

  bool find(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
};


signed main() {
  int N, M, K;
  cin >> N >> M >> K;
  UnionFind uf(N);
  vector<int> degree(N);
  vector<int> ans(N);

  for(int m=0; m<M; m++) {
    int a, b;
    cin >> a >> b;
    uf.union_(a-1, b-1);
    degree[a-1]++;
    degree[b-1]++;
  }

  //cerr << endl;
  for(int n=0; n<N; n++) {
    ans[n] = uf.size(n) - degree[n] - 1;
    //cerr << n << "\t" << uf.size(n) << "\t" << degree[n] << "\t" << ans[n] << endl;
  }

  for(int k=0; k<K; k++) {
    int c, d;
    cin >> c >> d;
    c--; d--;
    if(uf.find(c,d)) {
      ans[c]--;
      ans[d]--;
    }
  }

  cout << ans[0];
  for(int n=1; n<N; n++) {
    cout << " " << ans[n];
  }
  cout << endl;
}

Measured memory_bytes: 3200
#ifdef MY_LOCAL
#define MY_MAIN(cls) class cls {public: int main();}; int cls::
#else
#define MY_MAIN(cls) int
#endif

#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


ll gcd(ll a, ll b)
{
	if (a < b)
		swap(a, b);
	if (a % b == 0)
		return b;
	return gcd(b, a % b);
}

ll modpow(ll base, ll exponent, ll mod)
{
	ll retval = 1;
	while (exponent > 0)
	{
		if (exponent % 2)
			retval = (retval * base) % mod;
		exponent /= 2;
		base = (base * base) % mod;
	}
	return retval;
}


MY_MAIN(sandbox) main()
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	ll modval = 1000000007;

	int n;
	cin >> n;
	map<pll, int> cnt;
	for (int i = 0; i < n; i++)
	{
		ll a, b;
		cin >> a >> b;
		if (a != 0 && b != 0)
		{
			if (a < 0)
			{
				a *= -1;
				b *= -1;
			}
			ll g = gcd(abs(a), abs(b));
			cnt[{a / g, b / g}]++;
		}
		else if (a == 0 && b == 0)
			cnt[{0, 0}]++;
		else if (a == 0)
			cnt[{0, 1}]++;
		else  // b == 0
			cnt[{1, 0}]++;
	}

	ll num00 = 1;
	if (cnt[{0, 0}] == 0)
		num00 = 0;
	else
		num00 = cnt[{0, 0}];
	cnt.erase(make_pair(0,0));

	ll num = 1;
	while (!cnt.empty())
	{
		auto this_item = *cnt.begin();
		cnt.erase(cnt.begin());
		pll this_pair = this_item.first;
		pll anti_pair = { this_pair.second, -this_pair.first };
		if (anti_pair.first < 0)
			anti_pair = { -this_pair.second, this_pair.first };
		else if (anti_pair.first == 0)
			anti_pair = { 0, 1 };
		if (cnt.find(anti_pair) == cnt.end())
			cnt[anti_pair] = 0;
		auto anti_item = cnt.find(anti_pair);

		num = num * (modpow(2, this_item.second, modval) - 1 + modpow(2, anti_item->second, modval) - 1 + 1) % modval;
		cnt.erase(anti_item);
	}
	ll retval = (num + modval - 1) % modval;
	cout << (retval + num00) % modval << "\n";
		
	return 0;
}


Measured memory_bytes: 16028
#include<iostream>
#include<stdio.h>
#include<vector>
#include<ctype.h>
#include<string>
#include<cmath>
using namespace std;

void selectionSort(vector<int> A,int N){
    int counter=0;
    for(int i=0;i<N;++i){
        int minj=i;
        for(int j=i;j<N;++j){
            if(A[j]<A[minj]){
                minj=j;
            }
        }
        if(i!=minj){
            int buf=A[i];
            A[i]=A[minj];
            A[minj]=buf;
            counter++;
        }
    }
    for(int i=0;i<N;++i){
        if(i!=0)cout<<" ";
        cout<<A[i];
    }
    cout<<endl<<counter<<endl;
}

int N;
vector<int> A;

int main(){
    cin>>N;
    A.resize(N);
    for(int i=0;i<N;++i){
        cin>>A[i];
    }
    selectionSort(A,N);
    return 0;
}



Measured memory_bytes: 3160
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(){
    int a,b;
    char s[20];
    scanf("%d%d",&a,&b);
    scanf("%s",s);

    int flag=1;

    for(int i=0;i<=a+b;i++){
        if(i==a){
            if(s[a]!='-'){
                flag=0;
                break;
            }
        }
        else{
            if(!('0'<=s[i] && s[i]<='9')){
                flag=0;
                break;
            }
        }
    }

    if(flag){
        puts("Yes");
    }else{
        puts("No");
    }
    
    return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int t = sc.nextInt();
        int a = sc.nextInt();
        int[] h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();
        }
        sc.close();

        int ans = 0;
        double diff = Double.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            double temp = t - h[i] * 0.006;
            double abs = Math.abs(temp - a);
            if (abs < diff) {
                diff = abs;
                ans = i + 1;
            }
        }
        System.out.println(ans);
    }

}


Measured memory_bytes: 22228
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define ss second
#define ff first
#define INF 300000000000001
#define ll_max 9000000000000000001
#define mod 998244353
#define PI 3.14159265358979323846L
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
typedef vector<pair<ll,ll> > vll;
typedef vector<pair<int,int> > vii ;
typedef pair<ll,ll> pll;
const ll N = 1000001;
const ll M = 1;

struct point {
    ll x, y;
};

ll fast_exp(ll x, ll n)
{
    if(n == 0) return 1;
    else if(n & 1)
        return fast_exp(x, n - 1) * x % mod;
    else
    {
        ll tmp = fast_exp(x, n >> 1);
        return tmp * tmp % mod;
    }
}

bool c(string s)
{
    ll n = s.size();
    for(int i = 0; i < n / 2; i++)
    {
        if(s[i] != s[n - i - 1]) return false;
    }
    return true;
}

int main()
{
    fast;
    int _ = 1;
    //cin >> _;
    while(_--)
    {
        ll n, m = 0, ans = 0, x, y, k, v;
        cin >> n;
        ll cnt[n + 1] = {};
        ll a[n];
        for(int i = 0; i < n; i++) cin >> a[i], cnt[a[i]]++;
        for(int i = 0; i <= n; i++)
        {
            ans += cnt[i] * (cnt[i] - 1) >> 1;
        }
        for(int i = 0; i < n; i++)
        {
            cout << ans - cnt[a[i]] + 1 << "\n";
        }
    }
    return 0;
}


Measured memory_bytes: 5760
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> TUP;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define mp(a,b) make_pair(a,b)
const ll MOD=1000000007;

ll maxx(ll x,ll y,ll z){
	return max(max(x,y),z);
}
ll minn(ll x,ll y,ll z){
	return min(min(x,y),z);
}
ll gcd(ll x,ll y){
	if(x%y==0) return y;
    else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
	return x*y/gcd(x,y);
}

int main(){
    string s; cin>>s;
  	if(s[0]=='9' || s[1]=='9') cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast","unroll-loops")
#pragma GCC push_options
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include <xmmintrin.h>
#include <immintrin.h>
using namespace::std;
__attribute__((constructor))void init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
template<typename T>using pbds=__gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T>using pbds_map=__gnu_pbds::tree<T,T,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T,typename E>using hash_map=__gnu_pbds::gp_hash_table<T,E>;
template<typename T>using pqueue =__gnu_pbds::priority_queue<T, less<T>,__gnu_pbds::rc_binomial_heap_tag>;
typedef long long lint;
#define INF (1LL<<60)
#define IINF (1<<30)
#define EPS (1e-10)
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
template<typename T>inline void numout(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i<INF/2?i:"INF";f=1;}cout<<endl;}
template<typename T>inline void numout2(T t){for(auto i:t)numout(i);}
template<typename T>inline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}
template<typename T>inline void output2(T t){for(auto i:t)output(i);}
template<typename T>inline void _output(T t){bool f=0;for(int i=0;i<t.size();i++){cout<<f?"":" "<<t[i];f=1;}cout<<endl;}
template<typename T>inline void _output2(T t){for(int i=0;i<t.size();i++)output(t[i]);}
#define rep(i,n) for(int i=0;i<int(n);++i)
#define repi(i,a,b) for(int i=int(a);i<(int)(b);++i)
#define rrep(i,n) for(int i=int(n)-1;i>=0;--i)
#define rrepi(i,a,b) for(int i=int(b)-1;i>=int(a);--i)
#define irep(i,n) for(int i=int(n);;++i)
#define all(n) begin(n),end(n)
inline auto gcd(auto A,auto B){return B?gcd(B,A%B):A;}
inline auto lcm(auto A,auto B){return A/gcd(A,B)*B;}
inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;}
inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;}
const vector<lint> dx={-1,1,0,0,1,1,-1,-1};
const vector<lint> dy={0,0,-1,1,1,-1,1,-1};
#define SUM(v) accumulate(all(v),0LL)
auto call=[](auto f,auto... args){return f(f,args...);};

int main(){
    lint k,x;
    cin>>k>>x;
    cout<<(k*500>=x?"Yes":"No")<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define size_of_array(array) (sizeof(array)/sizeof(array[0]))
#define MAX 100005
#define DEBUG 0 
#define LIMIT (LONG_MAX / 10)
#define POSITIVE_LAST_D (LONG_MAX % 10)
using ll =long long;
using namespace std;
using Graph=vector<vector<int>>;

int main(){
    int k,x;
    cin>>k>>x;
    if(x<=500*k){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }

    return 0;
    }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main () {
  int n, alice = 0, bob = 0;
  cin >> n;
  int a[n];
  
  for (int i = 0; i < n; i++) cin >> a[i];

  sort(a, a + n, greater<int>());
  for (int i = 0; i < n; i++) {
    if(i % 2 == 0) alice += a[i];
    else bob += a[i];
  }
  cout << abs(alice - bob) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)
#define all(v) (v).begin(), (v).end()
#define eb emplace_back

int main(){
    i64 N, M;
    cin >> N >> M;
    vector<int> penalty(N, 0);
    vector<bool> ac(N, false);

    rep(i, M){
        int p;
        string s;
        cin >> p >> s; p--;
        if(ac[p]) continue;

        if(s == "AC") ac[p] = true;
        else penalty[p]++;
    }

    int AC = 0, WA =0;
    for(int i = 0; i < N; i++){
        if(ac[i]) {
            AC++;
            WA += penalty[i];
        }
    }

    cout << AC << " " << WA << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<ll, int>;

const ll INF = 1LL<<59;
int di[] = {-1, 0, 1, 0};
int dj[] = {0, -1, 0, 1};

int main(){
    int h, w, k;
    cin >> h >> w >> k;
    int si, sj, ti, tj;
    cin >> si >> sj >> ti >> tj;
    --si, --sj, --ti, --tj;
    vector<string> g(h);
    rep(i,h) cin >> g[i];

    auto toID = [&](int i, int j, int v){
        return (i * w + j) * 4 + v;
    };
    auto modCeilK = [&](ll x){
        return (x + k - 1)/k * k;
    };

    vector<ll> dist(h * w * 4, INF);
    priority_queue<P, vector<P>, greater<P>> q;

    auto push = [&](int i, int j, int v, ll x){
        int id = toID(i,j,v);
        if(dist[id] <= x) return;
        dist[id] = x;
        q.emplace(x, id);
    };

    rep(v,4) push(si, sj, v, 0);
    while(!q.empty()){
        ll d = q.top().first;
        int id = q.top().second;
        q.pop();
        //if(dist[id] != d) continue;
        int i = id/w/4;
        int j = id/4%w;
        int v = id%4;
        rep(nv,4) push(i,j,nv,modCeilK(d));
        {
            int ni = i + di[v], nj = j + dj[v];
            if(0 <= ni && ni < h && 0 <= nj && nj < w){
                if(g[ni][nj] == '.'){
                    push(ni, nj, v, d+1);
                }
            }
        }
    }
    ll ans = INF;
    rep(v,4) ans = min(ans, dist[toID(ti, tj, v)]);
    if(ans == INF){
        cout << -1 << endl;
    }else{
        ans = modCeilK(ans)/k;
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 44192
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
  	String s=sc.next();
    if(s.indexOf("C")!=-1&&s.lastIndexOf("F")!=-1&&s.indexOf("C")<s.lastIndexOf("F")){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }
}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
#define MOD 1000000000
#define MAX 10000005
#define ll long long
#define mp(a,b) make_pair(a,b)
#define FF first
#define SS second
#define pb(x) push_back(x)
#define ub upper_bound
#define lb lower_bound
#define clr(x) memset(x,0,sizeof(x))
#define sws ios::sync_with_stdio(false); cin.tie(0)
#define pi acos(-1)
#define rep(I, N) for (ll I = 0; I < (N); ++I)
#define repp(I, A, B) for (ll I = (A); I <= (B); ++I)
#define trace1(x)                cout<<#x<<": "<<x<<endl
#define trace2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
using namespace std;
ll pwr(ll base, ll p, ll mod = MOD)
{
    ll ans = 1;
    while(p)
    {
        if(p & 1)   ans = (ans * base) % MOD;
        base = (base * base) % MOD;
        p /= 2;
    }
    return ans;
}
// for inverse modulo : if (1/b)%mod then ans is (b^(mod-2))%mod
ll gcd(ll a, ll b)
{
    if(b == 0)  return a;
    return gcd(b, a%b);
}
ll lcm(ll a, ll b)
{
    return (a*b) / gcd(a, b);
}
bool isPrime[MAX];
void sieve(int n) 
{
    for(int i = 0; i <= n;++i) 
    {
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 2; i * i <= n; ++i) 
    {
         if(isPrime[i] == true) 
         {
             for(int j = i * i; j <= n ;j += i)
                 isPrime[j] = false;
        }
    }
}
bool cmp(const pair<int,int> &a, const pair<int,int> &b)
{
    return (a.first > b.first);
}
const ll N = 2e5 + 5 ;
int main()
{
    sws;
    //clock_t clk;
    //clk = clock();
    //freopen("A.in", "r", stdin); 
    //freopen("A.out", "w", stdout);

 
    map<ll,int> m;
    set<ll> s;
    int n;
    cin >> n;
    int cnt = 0;
    repp(i,1,n)
    {
        ll num;
        cin >> num;
        if(s.find(num) == s.end()) s.insert(num);
        else s.erase(num);
    }
    cout << (int)s.size();


    //clk = clock() - clk;
    //cout << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
    return 0;
}

Measured memory_bytes: 4992
def main():
    total = int(input())
    mod = 1000000007
    dp = [0] * (total + 1)
    dp[0] = 1
    for i in range(1, total + 1):
        right = max(0, i - 3 + 1)
        dp[i] = sum(dp[0: right]) % mod
    return dp[total]


if __name__ == '__main__':
    print(main())


Measured memory_bytes: 9084
#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
#include<vector>
#include<math.h>
#include<utility>
#include<iomanip>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int h, n;
	cin >> h >> n;
	int a;
	int dmg = 0;
	while (n--) {
		cin >> a;
		dmg += a;
	}

	if (dmg >= h) cout << "Yes";
	else cout << "No";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=(a); i<(b); i++)

int main() {
  int N;
  cin >> N;
  int a[2][N];
  FOR(i,0,2) {
    FOR(j,0,N) {
      cin >> a[i][j];
    }
  }
  FOR(i,0,2) {
    FOR(j,0,N) {
      if(i==0 && j==0) continue;
      else if(i==0 && j>0) {
        a[i][j] = a[i][j-1] + a[i][j];
      }
      else if(i==1 && j==0) {
        a[i][j] = a[i][j] + a[0][0];
      }
      else {
        a[i][j] = max(a[i-1][j], a[i][j-1]) + a[i][j];
      }
    }
  }
  cout << a[1][N-1] << endl;
  return 0;
  
}




Measured memory_bytes: 3596
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	vector<int> a = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
	int n;
	cin >> n;
	cout << a[n - 1] << "\n";

	return 0;
}


Measured memory_bytes: 380
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <iomanip>

using namespace std;

int main(){
   int N;
   cin >> N;
   long long ans=0;
   for(int i = 1; i <= N ; i ++){
      if(i%3!=0&&i%5!=0){
         ans += i;
      }
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>

using namespace std;

#define REP(i,m) for(int i=0; i<m; i++)
#define FOR(i,n,m) for(int i=n; i<m; i++)
#define INF 1000000007
#define INFL (1LL << 60)
#define MOD 998244353
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

int main(){
	string s;
	cin >> s;
	REP(i, s.size()){
		s[i] -= 3;
		if(s[i] < 'A') s[i] += 26;
	}
	cout << s << endl;
	return 0;
} 


Measured memory_bytes: 3208
#include "bits/stdc++.h"
 
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pl4 = pair<ll,ll>;
using str = string;
using vpl4 = vector<pair<ll,ll>>;

#define sz size()
#define be begin()
#define en end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define llin(x) ll (x);cin >>(x);
#define stin(x) str (x);cin >>(x);
#define FOR(i,a,b) for(ll i = a ; i <= b ; i++)
#define rFOR(i,b,a) for(ll i = a; i >= b ; i--)
#define SORT(x) sort(x.be, x.en)
#define rSORT(x) sort(x.rbegin(), x.rend())
#define say(x) cout<<(x);
#define sal(x) cout<<(x)<<endl;
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;
#define Imp(a) cout <<((a)?"Possible":"Impossible")<<endl;
#define IMP(a) cout <<((a)?"POSSIBLE":"IMPOSSIBLE")<<endl;

ll MOD=1000000007;

signed main(){
	llin(n);
	vll l(n);
	ll s=0;
	FOR(i,0,n-1){
		cin >>l[i];
		s+=l[i];
	}
	rSORT(l);
	Yn(s-l[0]>l[0]);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define db double
#define ls rt << 1
#define rs rt << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define eps 1e-9
#define clv(V) (V).clear()
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[(sz(V)-2)])
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define upmax(a,b) (a)=max((a),(b))
using namespace std;
const db pi = acos(-1.0);
inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

typedef long long ll;
typedef pair<ll, ll> pll;
ll operator * (pll a, pll b) { return a.X * b.Y - b.X * a.Y; }
ll ccw(pll a, pll b, pll c) { return a * b + b * c + c * a; }
struct Node
{
	vector<pll> V;
	void init() { clv(V); }
	void push(ll a, ll b)
	{
		for(; 1 < sz(V) && ccw(befv(V), V.back(), {a, b}) <= 0; V.pop_back());
		V.pb({a, b});
	}
	ll f(ll x, int idx) { return V[idx].X * x + V[idx].Y; }
	ll f(ll x)
	{
		if(V.empty()) return -INFLL;
		int s = 0, e = sz(V) - 1;
		for(int m; s < e;)
		{
			m = (s + e) / 2;
			ll l = f(x, m), r = f(x, m + 1);
			if(l < r) s = m + 1; 
			else e = m;
		}
		return f(x, s);
	}
};
const int Mn = 300010;
Node a;
ll L[Mn], R[Mn], P[Mn], S[Mn], T[Mn];
int N, M;

void f(ll d[]) 
{
	rep(i, 1, N) S[i] = S[i - 1] + T[i];
	a.init(); 
	a.push(0, 0);
	rep(i, 1, N)
	{
		d[i] = max(d[i - 1], a.f(i) + ((ll)i * i + i) / 2 - S[i]);
		a.push(-i, d[i] + S[i] + ((ll)i * i - i) / 2);
	}
}

void f(ll d[], int s, int e) 
{
	if(s > e) return;
	if(s == e) 
	{
		upmax(d[s], L[s - 1] + R[s + 1] + 1 - T[s]);
		return;
	}
	int m = (s + e) / 2; 
	ll x = -INFLL;
	a.init();
	rep(j, m + 1, e)
		a.push(-j, R[j + 1] - S[j] + ((ll)j * j + 3 * j) / 2);
	rep(i, s, m) 
	{
		ll t = a.f(i) + L[i - 1] + S[i - 1] + ((ll)i * i - 3 * i + 2) / 2;
		upmax(x, t); 
		upmax(d[i], x);
	}
	a.init(); 
	x = -INFLL;
	rep(i, s, m)
		a.push(-i, L[i - 1] + S[i - 1] + ((ll)i * i - 3 * i) / 2);
	for(int j = e; m < j; j --) 
	{
		ll t = a.f(j) + R[j + 1] - S[j] + ((ll)j * j + 3 * j + 2) / 2;
		upmax(x, t); 
		upmax(d[j], x);
	}
	f(d, s, m); 
	f(d, m + 1, e);
}

int main()
{
	scanf("%d", &N);
	rep(i, 1, N) scanf("%lld", &T[i]);
	f(L); reverse(T + 1, T + N + 1);
	f(R); reverse(R + 1, R + N + 1);
	reverse(T + 1, T + N + 1);
	rep(i, 1, N) S[i] = S[i  -1] + T[i];
	fill(P + 1, P + N + 1, -INFLL);
	f(P, 1, N);
	M = read();
	while(M --)
	{
		int p = read();
		ll x;
		scanf("%lld", &x);
		printf("%lld\n", max(0ll, max(L[p - 1] + R[p + 1], P[p] + T[p] - x)));
	}
	return 0;
}


Measured memory_bytes: 14336
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int main()
{
	string S;
	cin >> S;
	int ans = 0;
	for (int i = 0; i < S.size() - 1; i++) {
		if (S[i] != S[i + 1]) ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


namespace AtCoder
{
    class Program
    {

        const int BiggestMod = 1000000007;

        static void Main()
        {

            var num = int.Parse(Console.ReadLine());
            var str = Console.ReadLine();

            if (str.Length <= num)
                Console.WriteLine(str);
            else
            {

                Console.WriteLine(str.Substring(0, num) + "...");

            }

        }
    }
}


Measured memory_bytes: 27476
#include<iostream>
#define REP1(i, n) for (int i = 1; i <= (int)(n); ++i)

using namespace std;

int main() {
  int n; cin >> n;
  REP1(i, n) {
    int x = i;
    if (x % 3 == 0) {
      cout << ' ' << i;
      continue;
    }
    while (x) {
      if (x % 10 == 3) {
        cout << ' ' << i;
        break;
      }
      x /= 10;
    }
  }
  cout << endl;
}


Measured memory_bytes: 3128
import java.io.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] array = br.readLine().split(" ");
        int num = Integer.parseInt(array[0]);
        int min=num,max=num;
        long sum=num;
        for(int i=1;i<N;i++){
            num=Integer.parseInt(array[i]);
            if(num<min) min=num;
            if(num>max) max=num;
            sum+=num;
        }
        System.out.println(min+" "+max+" "+sum);
	}
}

Measured memory_bytes: 25496
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <climits>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cassert>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

const ll MOD = ll(1e9 + 7);
const ll INF = LLONG_MAX;
const ll MAX_N = ll(1e3) + 5;
const double EPS = 10e-8;
const double PI = 3.14159265359;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)

int main() {
    int a,b,c;
    cin >> a >> b;
    c=b-a;
    c = c*(c-1)/2;
    cout << c-a << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>

#define DIV 1000000007

using namespace std;

long long N, M, Q;
long long S[100005];
long long T[100005];
long long origin;

vector<pair<long long , long long> >tree[4005];

long long memo[4005][4005];

vector<pair<long long, pair<long long, long long> > >fvec;

// 素集合データ構造
struct UnionFind
{
  // par[i]：データiが属する木の親の番号。i == par[i]のとき、データiは木の根ノードである
  vector<int> par;
  // sizes[i]：根ノードiの木に含まれるデータの数。iが根ノードでない場合は無意味な値となる
  vector<int> sizes;

  UnionFind(int n) : par(n), sizes(n, 1) {
	  // 最初は全てのデータiがグループiに存在するものとして初期化
	  for(int i = 0; i < n; i++){
		  par[i] = i;
	  }
  }

  // データxが属する木の根を得る
  int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);  // 根を張り替えながら再帰的に根ノードを探す
  }

  // 2つのデータx, yが属する木をマージする
  void unite(int x, int y) {
    // データの根ノードを得る
    x = find(x);
    y = find(y);

    // 既に同じ木に属しているならマージしない
    if (x == y) return;

    // xの木がyの木より大きくなるようにする
    if (sizes[x] < sizes[y]) swap(x, y);

    // xがyの親になるように連結する
    par[y] = x;
    sizes[x] += sizes[y];
    // sizes[y] = 0;  // sizes[y]は無意味な値となるので0を入れておいてもよい
  }

  // 2つのデータx, yが属する木が同じならtrueを返す
  bool same(int x, int y) {
    return find(x) == find(y);
  }

  // データxが含まれる木の大きさを返す
  int size(int x) {
    return sizes[find(x)];
  }
};


void prepare(){
	UnionFind uf(N + 1);	

	set<long> done;
	long long ans = 0;
	for(int i = 0; i < fvec.size(); i++){
		long long src = fvec[i].second.first;
		long long dst = fvec[i].second.second;
		long long cost = fvec[i].first;
		if(uf.same(src, dst) == false){
			uf.unite(src, dst);
			tree[src].push_back(make_pair(cost, dst));
			tree[dst].push_back(make_pair(cost, src));
			origin += cost;
		}
		if(uf.size(0) == N){
			return;
		}
	}
}

void dfs(long long root, long long pa, long long cur, long long maxi){
	//cout << " root " << root << " pa " << pa << " cur " << cur << endl;
	memo[root][cur] = maxi;
	for(int i = 0; i < tree[cur].size(); i++){
		long long cost = tree[cur][i].first;
		long long next = tree[cur][i].second;
		if(pa != next){
			dfs(root, cur, next, max(maxi, cost));
		}
	}
}

int main(){
	cin >> N >> M;
	for(int i = 0; i < M; i++){
		long long a, b, c;
		cin >> a >> b >> c;
		a--;b--;
		fvec.push_back(make_pair(c, make_pair(a, b)));
	}

	sort(fvec.begin(), fvec.end());


	cin >> Q;
	for(int i = 0; i < Q; i++){
		cin >> S[i] >> T[i];
		S[i]--;T[i]--;
	}
	prepare();
	for(int i = 0; i < N; i++){
		dfs(i, -1, i, 0);
	}
	/*
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			cout << i << " -> " << j << ":" << memo[i][j] << endl;
		}
	}
	*/

	for(int i = 0; i < Q; i++){
		cout << origin - memo[S[i]][T[i]] << endl;
	}
}

Measured memory_bytes: 137832
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int, int>
#define vi vector<int>
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(v) v.begin(), v.end()
#define x first
#define y second
#define rep(i, j, k) for(i=j; i<k; i++)
#define sep(i, j, k) for(i=j; i>k; i--)
const int N = 2e5+5, inf = 1e9+7;
int n, k, i, j;
int A[N], h[N];  
vi bit(N);
void upd(int x,int val){
    for(;x<=n;x+=(x&-x))
        bit[x] = max(bit[x], val);
}
int q(int x){
    int res=0;
    for(;x>0;x-=(x&-x))
        res = max(res, bit[x]);
    return res;
}
signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int i, j, a, b, ans = 0;
    cin>>n;
    rep(i, 1, n+1) cin>>h[i];
    rep(i, 1, n+1) cin>>A[i];
    rep(i, 1, n+1){
        a = q(h[i]-1);
        upd(h[i], a+A[i]);
    }
    cout<<q(n);
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define sz(c)      int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
using ll = long long;

int const MAXN=110000;
int N;
int S[MAXN];

map<pair<int,int>,ll> f[MAXN];

ll get_sum_naive(int s,int d,int k) {
	if (f[s].count({d,k})) return f[s][{d,k}];
	ll sum=0;
	rep(i,0,k+1) sum+=S[s+i*d];
	f[s][{d,k}]=sum;
	return sum;
}

ll check_naive(int A,int d) {
	if (A<=d) return 0;
	int k=(N-1-A)/d;
	if (A%d==0 && k>=A/d) return 0;
	return get_sum_naive(0,d,k) + get_sum_naive(A,d,k);
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	cin>>N;
	rep(i,0,N) cin>>S[i];
	
	ll res=0;
	for (int d=1; d*d<=N; ++d) {
		vector<vector<ll>> sums(d);
		rep(i,0,N) {
			ll v=S[i];
			if (!sums[i%d].empty()) v+=sums[i%d].back();
			sums[i%d].push_back(v);
		}
		
		rep(A,1,N-1) if ((N-1-A)%d==0) {
			int k=(N-1-A)/d;
			res=max(res,check_naive(A,k));
			
			if (A<=d || (A%d==0 && k>=A/d)) continue;
			
			ll sum=sums[0][k];
			sum+=sums[A%d][A/d+k];
			if (A/d>0) sum-=sums[A%d][A/d-1];
			res=max(res,sum);
		}
	}
		
	cout<<res<<"\n";
}


Measured memory_bytes: 73828
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 29;
 
int main() {
	int n, k, q;
	cin >> n >> k >> q;
	vector<int> correct(n, 0);
	rep(i, q) {
		int a; cin >> a;
		correct[a-1]++;
	}
	rep(i, n) {
		int score = k - q + correct[i];
		if (score > 0) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
int main(void){
    // Your code here!
    int a,b,c,cnt=0;
    scanf("%d %d %d",&a,&b,&c);
    if(a!=b) cnt++;
    if(a!=c) cnt++;
    if(b!=c) cnt++;
    if(a==b && b==c) cnt=1;
    printf("%d",cnt);
}


Measured memory_bytes: 128
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;
const int kmax = 510000;

long long fact[kmax], fact_inv[kmax], inv[kmax];

int gcd(int a, int b)
{
    if (!b) {
        return a;
    }

    return gcd(b, a % b);
}

void init_comb()
{
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < kmax; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int r)
{
    if (n < r) {
        return 0;
    }

    if (n < 0 || r < 0) {
        return 0;
    }

    return fact[n] * (fact_inv[r] * fact_inv[n - r] % mod) % mod;
}

template <typename T, T N>
class UnionFind {
    T parent_[N];
    T rank_[N];
    T size_[N];

public:
    UnionFind();
    T Root(T idx);
    bool IsSame(T x, T y);
    void Unite(T x, T y);
    T GetSize(T idx);
};

template <typename T, T N>
UnionFind<T, N>::UnionFind()
{
    for (T i = 0; i < N; i++) {
        parent_[i] = i;
        rank_[i] = 0;
        size_[i] = 1;
    }
}

template <typename T, T N>
T UnionFind<T, N>::Root(T idx)
{
    return parent_[idx] == idx ? idx : parent_[idx] = Root(parent_[idx]);
}

template <typename T, T N>
bool UnionFind<T, N>::IsSame(T x, T y)
{
    return Root(x) == Root(y);
}

template <typename T, T N>
void UnionFind<T, N>::Unite(T x, T y)
{
    x = Root(x);
    y = Root(y);
    if (x == y) {
        return;
    }

    if (rank_[x] < rank_[y]) {
        parent_[x] = y;
        size_[y] += size_[x];
    } else {
        parent_[y] = x;
        size_[x] += size_[y];
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

template <typename T, T N>
T UnionFind<T, N>::GetSize(T idx)
{
    return size_[Root(idx)];
}

int main()
{
    int n;
    std::cin >> n;

    std::vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    long long rgb_num[3] = { 0, 0, 0 };
    long long multiplier = 3;

    long long ans = 1;

    for (auto num : a) {
        long long multiplier = 0;
        for (int i = 0; i < 3; i++) {
            if (rgb_num[i] == num) {
                multiplier++;
            }
        }

        for (int i = 0; i < 3; i++) {
            if (rgb_num[i] == num) {
                rgb_num[i]++;
                break;
            }
        }

        ans *= multiplier;
        ans %= mod;
    }

    std::cout << ans << std::endl;
}


Measured memory_bytes: 1024
mod=10**9+7
N,M=map(int,input().split())
A=[int(input()) for m in range(M)]
L=[1 for n in range(N+1)]
for a in A:
    L[a]=0
Block=[0,1]
for n in range(1,N+1):
    if L[n]==1:
        Block=Block[1:]+[sum(Block)%mod]
        
    else:
        Block=Block[1:]+[0]
print(Block[-1])

Measured memory_bytes: 7800
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    vector<int> a(3);
    rep(i, 3) cin >> a[i];
    sort(a.begin(), a.end());
    int ans = 0;
    ans += a[1] - a[0];
    ans += a[2] - a[1];
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void YN(bool flg){if(flg) cout << "YES" << endl; else cout << "NO" << endl;}
void Yn(bool flg){if(flg) cout << "Yes" << endl; else cout << "No" << endl;}
void yn(bool flg){if(flg) cout << "yes" << endl; else cout << "no" << endl;}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

ll g(ll n) {return n*(n+1)/2;}

int main()
{   
    ll n;
    cin >> n;
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        ans += i*g(n/i);
    }
    cout << ans << endl;
        
    return 0;
}


Measured memory_bytes: 3596
import sys

read = sys.stdin.buffer.read
INF = 1 << 60


def main():
    H, N, *AB = map(int, read().split())

    dp = [INF] * (H + 1)
    dp[0] = 0

    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H + 1):
            if dp[i] > dp[max(i - a, 0)] + b:
                dp[i] = dp[max(i - a, 0)] + b

    print(dp[H])
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 70496
use std::io::*;
use std::str::FromStr;
 
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}
 
#[allow(non_snake_case, unused_variables)]
fn main() {
    let S: Vec<char> = read::<String>().chars().collect();
    let ans = 
        if S[0]=='A'
            && S[2..S.len()-1].iter().filter(|c| **c=='C').count()==1 
            && S.iter().fold(0,|sum,c| sum + c.is_uppercase() as i32)==2 {
            "AC"
        } else {
            "WA"
        };
    println!("{}", ans);
}



Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define F first
#define S second
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define INF 0x3f3f3f3f
#include<ext/rope>
using namespace __gnu_cxx;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef pair<double,double> pdd;
ll a,b;
int main()
{
    //IOS;
    while(cin>>a>>b)
    {
        cout<<max(0LL,a-2*b)<<'\n';
    }
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
	string s;
	cin >> s;
	vector<char> vec (s.size());
	for(int i = 0;i < s.size();i++){
		vec.at(i) = s.at(i);
	}
	sort(vec.begin(),vec.end());
	char test = 'a';
	for(int i = 0;i < s.size();i++){
		if(vec.at(i) == test){
			if(test < 'z'){
				test++;
			}
			else{
				cout << "None" << endl;
				return 0;
			}
		}
		else if(vec.at(i) < test){
			
		}
		else if(vec.at(i) > test){
			break;
		}
	}
	cout << test << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;

int main(){
 string S,T;
  cin >>S;
  cin >>T;
  
  int cnt=0;
  for(int i=0;i<S.size();i++){
    if(S[i]!=T[i]){
      cnt++;
    }
  }
  cout <<  cnt <<endl;
}

 

Measured memory_bytes: 3848
#include<iostream>
using namespace std;
typedef long long ll;

int main(){
    ll q,h,s,d,n;
    cin>>q>>h>>s>>d>>n;

    ll m=min(4*q,min(2*h,s));
    cout<<min(d*(n/2)+m*(n%2),m*n)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int s;
  int count = 0;
  
  cin >> s;
  
  count += s % 10;
  s /= 10;
  count += s % 10;
  s /= 10;
  count += s % 10;
  s /= 10;
  
  cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const ll mod = 1e9 + 7;
const ll inf = 1e18;

int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    ll x, n;
    cin >> x >> n;
    vll used(102);
    ll p;
    REP(i, n) {
        cin >> p;
        used[p] = 1;
    }
    ll res, diff = 1000;
    REP(i, 102) {
        if (used[i]) continue;
        if (chmin(diff, abs(x - i))) res = i;
    }
    cout << res << endl;
}

Measured memory_bytes: 3632
# -*- coding: utf-8 -*-
n = int(input())
a = [int(_) for _ in input().split()]

# my initial trial below ##############################
# from itertools import combinations
# combs = combinations(range(1, n), 3)
# grief = 10**10
# for comb in combs:
#     p = sum(a[:comb[0]])
#     q = sum(a[comb[0]:comb[1]])
#     r = sum(a[comb[1]:comb[2]])
#     s = sum(a[comb[2]:])

#     tmp = max(p, q, r, s) - min(p, q, r, s)
#     if tmp < grief:
#         grief = tmp

# print(grief)  # running time limit error

# solution below ######################################

cumul_sum = [0]
for i, ai in enumerate(a):
    cumul_sum.append(ai + cumul_sum[i])


def cal_sum(left, right):
    return cumul_sum[right] - cumul_sum[left]


def two_pointers(l, r, split, diff):
    for i in range(split, r):
        tmp_diff = abs(cal_sum(l, i) - cal_sum(i, r))
        if diff >= tmp_diff:
            diff = tmp_diff
        else:
            return i - 1, diff
    else:
        return r - 1, diff


l_split = 1
r_split = 3
griefs = []
for i in range(2, n - 1):
    # left
    l_split, l_diff = two_pointers(0, i, l_split, 10**12)
    # right
    r_split, r_diff = two_pointers(i, n, r_split, 10**12)

    p, q, r, s = cal_sum(0, l_split), cal_sum(l_split,
                                              i), cal_sum(i, r_split), cal_sum(
                                                  r_split, n)
    griefs.append(max(p, q, r, s) - min(p, q, r, s))


print(min(griefs))


Measured memory_bytes: 28972
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std;

const double PI = acos(-1.0);

template<typename T>
int LIS(const vector<T>& v){
    if(v.empty()) return 0;
	vector<T> a(v.size(), v[0]);
    auto end = a.begin();
    ++end;
	for(int i=1;i<v.size();i++){
		auto l = lower_bound(a.begin(), end, v[i]);
        if(l == end) ++end;
        *l = v[i];
	}
	return distance(a.begin(), end);
}

int main(){
    int x1, y1, x2, y2;
    while(cin >> x1 >> y1 >> x2 >> y2){
        if(y1 > y2){
            swap(x1, x2);
            swap(y1, y2);
        }
        int sgn = (x1 <= x2 ? 1 : -1);
        x1 *= sgn;
        x2 *= sgn;
        int N; cin >> N;
        vector<pair<int, int>> vp;
        for(int i=0;i<N;i++){
            int x, y; cin >> x >> y;
            x *= sgn;
            if(x1 <= x && x <= x2 && y1 <= y && y <= y2){
                vp.emplace_back(x, y);
            }
        }
        int width = min(x2-x1, y2-y1) + 1;
        double res = 1e12;
        for(int _=0;_<2;_++){
            sort(vp.begin(), vp.end());
            vector<int> v(vp.size());
            for(int i=0;i<v.size();i++) v[i] = vp[i].second;
            int l = LIS(v);
            if(l == width){
                res = min(100.0*(x2-x1+y2-y1) + 5*PI + l * (5*PI - 20), res);
            } else {
                res = min(100.0*(x2-x1+y2-y1) + l * (5*PI - 20), res);
            }
            for(auto& p : vp) swap(p.first, p.second);
        }
        printf("%.12lf\n", res);
    }
}


Measured memory_bytes: 3312
#include "bits/stdc++.h"

using namespace std;

int main() {
	int X, Y;
	cin >> X >> Y;
	if (Y < X) {
		cout << "No" << endl;
		return 0;
	}
	if (X == 0 || Y == 0) {
		cout << "No" << endl;
		return 0;
	}
	if (X == 1 && (Y % 2 == 0 || Y % 4 == 0)) {
		cout << "Yes" << endl;
		return 0;
	}
	if (X * 2 == Y || X * 4 == Y) {
		cout << "Yes" << endl;
		return 0;
	}
	if ((X - 1) * 2 + 4 == Y) {
		cout << "Yes" << endl;
		return 0;
	}
	for (int i = 0; i < X+1; i++) {
		for (int j = 1; j < X-1; j++) {
			if (j * 2 + i * 4 == Y && j + i == X) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>

using namespace std;

template <typename T> T gcd(T x, T y) {
  if (y == 0)
    return x;
  return gcd(y, x % y);
}

template <typename T> T lcm(T x, T y) {
  if (x == 0 || y == 0)
    return 0;
  return x / gcd(x, y) * y;
}

int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}

vector<int> p;
vector<int> r;

void init(int n) {
  p.reserve(n);
  r.resize(n);
  for (int i = 0; i < n; i++) {
    p[i] = i;
    r[i] = 0;
  }
}

int root(int x) { return p[x] == x ? x : p[x] = root(p[x]); }

bool same(int x, int y) { return root(x) == root(y); }

void unite(int x, int y) {
  x = root(x);
  y = root(y);
  if (x == y)
    return;

  if (r[x] < r[y])
    p[x] = y;
  else {
    p[y] = x;
    if (r[x] == r[y])
      r[x]++;
  }
}

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (abs(a - c) <= d || (abs(a - b) <= d && abs(b - c) <= d))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}


Measured memory_bytes: 256
n = int(input())
A = []
B = []
for i in range(n):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)

ans = 0
now = 0
for i in range(n-1,-1,-1):
    check = (A[i]+now)%B[i]
    if not check:
        continue
    tmp = B[i] - check
    ans += tmp
    now += tmp

print(ans)

Measured memory_bytes: 85608