akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int infI=1e9+5;
const long long infL=1e16;
const int MOD=1e9+7;
const int MAX=2e5+5;

#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define iii pair<ii,int>
#define ll long long
#define pll pair<ll,ll>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define forn(i,a,b) for(ll i=a;i<b;i++)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define endl '\n'
#define popb pop_back()
#define se second
#define fi first
#define test(t) int t;cin>>t;while(t--)
#define debug(x) cerr<<"=>"<<#x<<" = "<<x<<endl

ll power(ll a,ll b){
    if(b==0){
        return 1;
    }
    if(b==1){
        return a;
    }
    ll temp=power(a,b/2);
    temp=(temp*temp)%MOD;
    if(b%2){
        temp=(temp*a)%MOD;
    }
    return temp;
}

//only use if mod is prime
ll mod_inv(ll a,ll mod){
    a%=mod;
    return power(a,mod-2);
}

void extended_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    ll x1,y1;
    extended_gcd(b,a%b,x1,y1);
    x=y1;
    y=x1-((a/b)*y1);
    return;
}

//TLE can also occur if vectors are not passed by reference, debug statements can also cause TLE.
//priority_queue implements max heap by default

int main(){
    fastio;
    // think about edge cases like n=1(especially graph questions).
    int a[4]={};
    int n;
    cin>>n;
    forn(i,0,n){
        string s;
        cin>>s;
        if(s[0]=='A'){
            ++a[0];
        }
        if(s[0]=='W'){
            ++a[1];
        }
        if(s[0]=='T'){
            ++a[2];
        }
        if(s[0]=='R'){
            ++a[3];
        }
    }
    cout<<"AC x "<<a[0]<<endl;
    cout<<"WA x "<<a[1]<<endl;
    cout<<"TLE x "<<a[2]<<endl;
    cout<<"RE x "<<a[3]<<endl;
    return 0;
}

Measured memory_bytes: 3656
# -*- coding: utf-8 -*-
n = int(input())
b = list(map(int, input().split()))

sum = b[0]
for i in range(n-2):
  if b[i] >= b[i+1]:
    sum += b[i+1]
  else:
    sum += b[i]
sum += b[n-2]
print(sum)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=200005;
int n,par[max_n];
int findpar(int x){
    return x==par[x]?x:par[x]=findpar(par[x]);
}
int sx[max_n],sy[max_n];
void unite(int x,int y){
    x=findpar(x);y=findpar(y);
    if(x!=y){
        par[x]=y;
        sx[y]+=sx[x],sy[y]+=sy[x];
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<max_n;i++){
        par[i]=i;
        if(i<=100000)sx[i]=1;
        else sy[i]=1;
    }
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        unite(x,y+100000);
    }
    ll ans=0;
    for(int i=1;i<max_n;i++){
        if(findpar(i)==i){
            ans+=1ll*sx[i]*sy[i];
        }
    }
    ans-=n;
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 2176
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=4e4+5,maxm=4e5+5;
const ll inf=1e18;
inline int fa(int u){ return u/2; }
inline int ls(int u){ return u*2; }
inline int rs(int u){ return u*2+1; }
struct heap{
	int hea[maxn],pos[maxn],siz;
	ll *dis;
	heap(ll a[],int n){
		dis=a; siz=n;
		int i;
		for (i=1;i<=n;i++){
			dis[i]=inf; hea[i]=i; pos[i]=i;
		}
	}
	void hswap(int u,int v){
		swap(hea[u],hea[v]);
		pos[hea[u]]=u; pos[hea[v]]=v;
	}
	void update(int u){
		if (u==1) return;
		if (dis[hea[fa(u)]]<=dis[hea[u]]) return;
		hswap(u,fa(u));
		update(fa(u));
	}
	void pushdown(int u){
		int v=u;
		if (ls(u)<=siz&&dis[hea[ls(u)]]<dis[hea[v]]) v=ls(u);
		if (rs(u)<=siz&&dis[hea[rs(u)]]<dis[hea[v]]) v=rs(u);
		if (u==v) return;
		hswap(u,v);
		pushdown(v);
	}
	void change(int u,ll val){
		dis[u]=val;
		update(pos[u]);
		pushdown(pos[u]);
	}
	int pop(){
		hswap(1,siz);
		siz--;
		pushdown(1);
		return hea[siz+1];
	}
};
struct gragh{
	int head[maxn],next[maxm],to[maxm],tot;
	ll wei[maxm],cost[maxn];
	gragh(){
		memset(head,-1,sizeof(head));
		tot=0;
	}
	void clear(){
		memset(head,-1,sizeof(head));
		tot=0;
	}
	void add(int u,int v,ll w,ll c){
		next[tot]=head[u];
		head[u]=tot;
		to[tot]=v;
		wei[tot]=w;
		cost[tot]=c;
		tot++;
	}
	void dijkstra(ll dis[],ll val[],int st,int n){
		heap hp(dis,n);
		hp.change(st,0);
		int i,u,v,ed;
		for (i=1;i<=n;i++) val[i]=inf;
		val[st]=0;
		while (hp.siz){
			u=hp.pop();
			for (ed=head[u];ed!=-1;ed=next[ed])
				if (dis[v=to[ed]]>dis[u]+wei[ed])
					hp.change(v,dis[u]+wei[ed]);
		}
		for (u=1;u<=n;u++) for (ed=head[u];ed!=-1;ed=next[ed])
			if (dis[v=to[ed]]==dis[u]+wei[ed])
			val[v]=min(val[v],cost[ed]);
	}
};
gragh g;
ll dis[maxn],val[maxn];
int main(){
	int n,m,i,u,v;
	ll w,c,ans;
	while (scanf("%d%d",&n,&m)&&(n||m)){
		g.clear();
		for (i=0;i<m;i++){
			scanf("%d%d%lld%lld",&u,&v,&w,&c);
			g.add(u,v,w,c);
			g.add(v,u,w,c);
		}
		g.dijkstra(dis,val,1,n);
		ans=0;
		for (i=1;i<=n;i++) ans+=val[i];
		printf("%lld\n",ans);
	}
	return 0;
}


Measured memory_bytes: 4448
H, W = map(int, input().split())
# H, W = 100000, 2
# H, W = 100000, 100000

if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    def solve(H, W):
        ans = float('inf')
        for h in range(1, H):
            sa = W * h
            w = W // 2
            sb = w * (H - h)
            if W - w > 0:
                sc = (W - w) * (H - h)
                ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))

            rh = (H - h) // 2
            if (H - h - rh) > 0:
                sb = W * rh
                sc = W * (H - h - rh)
                ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))
        return ans
    ans = min(solve(H, W), solve(W, H))
    print(ans)


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

using namespace std;

int main(void) {
  int N;
  string S;
  cin >> N >> S;

  int ans = 0;
  for (int i = 0; i < N-2; i++) {
    if (S.substr(i, 3) == "ABC") ans++;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define ar array
#define mp make_pair
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	ll ans2 = (n/15)*200;
	ll ans = (n)*800;
	cout<<ans-ans2<<endl;
	return 0;
}

Measured memory_bytes: 256
s=input()+'R'

n=len(s)

C=[0]*n

cnt_r=0
cnt_l=0


def calc(tmp_r,tmp_l,cnt_r,cnt_l):        
    C[tmp_r]=(cnt_r-1)//2+cnt_l//2+1
    C[tmp_l]=cnt_r//2+(cnt_l-1)//2+1

for i in range(n-1):
    if s[i]=='R' and s[i+1]=='R':
        cnt_r+=1
    
    if s[i]=='R' and s[i+1]=='L':
        cnt_r+=1
        tmp_r=i
        tmp_l=i+1
        
    if s[i]=='L' and s[i+1]=='R':
        cnt_l+=1
            
        calc(tmp_r,tmp_l,cnt_r,cnt_l)
        
        cnt_r=0
        cnt_l=0
    if s[i]=='L' and s[i+1]=='L':
        cnt_l+=1
    

        

print(*C[:-1])

Measured memory_bytes: 6376
import java.io.*;
import java.util.*;

class Main {
  int[][] map;
  int V;
  int E;
  boolean[] used;

  public int traverse(int current, int minNum) {
    if (current == V - 1) {
      return minNum;
    }

    used[current] = true;

    for (int i = 0; i < V; i++) {
      if (Integer.MAX_VALUE != map[current][i] && 0 < map[current][i] && !used[i]) {

        int d = traverse(i, Math.min(minNum, map[current][i]));
        if (d > 0) {
          map[current][i] -= d;
          map[i][current] += d;
          return d;
        }
      }
    }
    return 0;
  }

  public void run() {
    Scanner sc = new Scanner(System.in);
    V = sc.nextInt();
    E = sc.nextInt();

    map = new int[V][V];

    for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
        map[i][j] = Integer.MAX_VALUE;
      }
    }

    // input
    for (int i = 0; i < E; i++) {
      int u = sc.nextInt();
      int v = sc.nextInt();
      int c = sc.nextInt();

      map[u][v] = c;
      map[v][u] = 0;
    }

    int ans = 0;

    while (true) {
      used = new boolean[V];
      int d = traverse(0,  Integer.MAX_VALUE);
      if (d == 0) break;
      ans += d;
    }

    System.out.println(ans);
  }

  public static void main(String[] args) {
    new Main().run();
  }
}



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

int main() {
  int D,T,S;
  double x;
  cin>>D>>T>>S;
  x=(double)D/(double)S;
  if(x<=T){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define COUT(x) cout<<(x)<<"\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, n) for(int i=0;i<n;i++)
#define YES(x) cout<<(x?"YES":"NO")<<"\n"
#define Yes(x) cout<<(x?"Yes":"No")<<"\n"
#define dump(x) cout<<#x<<" = "<<(x)<<"\n"
#define endl "\n"
using G = vector<vector<int>>;
using M = map<int,int>;
using P = pair<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int,vector<int>,greater<int>>;
using V = vector<int>;
using ll = long long;
using edge = struct { int to; int cost; };
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 int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

/*
int h,w,d,q;
int a[301][301];
int l[90010],r[90010];
int s[90010];
vector<P> p(90010);
*/

int H,W,D,y[90001],x[90001],d[90001];
int main() {
  /*
  cin >> h >> w >> d;
  REP(i,h) REP(j,w) cin >> a[i][j];
  cin >> q;
  REP(i,q) cin >> l[i] >> r[i];

  REP(i,h) REP(j,w) p[a[i][j]] = {i,j};

  for (int i=1; i<=h*w-d; i++) {
    s[i+d] = s[i] + abs(p[i+d].first - p[i].first) + abs(p[i+d].second - p[i].second);
  }

  REP(i,q) COUT(s[r[i]] - s[l[i]]);
  return 0;
  */
	cin>>H>>W>>D;
	REP(i,H)
		REP(j,W){
			int A;
			cin>>A;
			y[A]=i,x[A]=j;
		}
	for(int i=D+1;i<=H*W;i++)
		d[i]=d[i-D]+abs(x[i-D]-x[i])+abs(y[i-D]-y[i]);
	cin>>D;
	REP(i,D){
		cin>>H>>W;
		cout<<d[W]-d[H]<<endl;
	}
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
using V = vector<ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define INF 1000000000

void solve_abc_b() {
	ll n;
	ll ans = 0;

	cin >> n;

	ll a;
	rep(i, n) {
		a = i + 1;
		if (a % 3 == 0 || a % 5 == 0) {

		}
		else {
			ans += a;
		}
	}

	cout << ans << "\n";
}

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

	solve_abc_b();

	return 0;
}

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

using namespace std;
#define ll long long
const long double EPS = 1e-8;
const long double PI = acos(-1);
const int N = 300 + 2;
const int mod = 1e9 + 7;
double mem[N][N][N];
int freq[4];
int n;

double solve(int i, int j, int k) {
    if (i + j + k == 0)return 0.0;
    if (mem[i][j][k] == mem[i][j][k])return mem[i][j][k];
    double waste = ((double) n - (i + j + k)) / n;
    double s = waste / (1 - waste); // waste of zeros
    double ret = 0;
    if (i)
        ret += (solve(i - 1, j, k) + s+1) * ((double) i / (i + j + k));
    if (j)
        ret += (solve(i + 1, j - 1, k) + s+1) * ((double) j / (i + j + k));
    if (k)
        ret += (solve(i, j + 1, k - 1) + s+1) * ((double) k / (i + j + k));
    return mem[i][j][k] = ret;
}

int main() {
    cin >> n;
    memset(mem, -1, sizeof mem);
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        freq[tmp]++;
    }
    cout <<fixed<<setprecision(10)<< solve(freq[1], freq[2], freq[3]) << endl;
}


Measured memory_bytes: 215552
#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using namespace std;
using lli = long long int;
int ver(vector<lli> a)
{
    lli cnt = 0;
    while (1) {
        sort(a.begin(), a.end());
        reverse(a.begin(), a.end());

        lli h = a.size();
        if (a[0] < h)
            return cnt;

        cnt++;
        a[0] -= h;
        rep(i, h - 1) a[i + 1]++;
    }
}
int main()
{
    lli k;
    cin >> k;
    lli h = 1e16;
    lli n = (k / h) + 2;
    if (n > 50) {
        n = 50;
    }

    vector<lli> a(n, n + k / n);
    rep(i, k % n) a[i] -= i;
    rep(i, n - k % n) a[k % n + i] -= k % n + 1;

    cout << n << endl;
    rep(i, n)
    {
        cout << a[i] << " ";
    }
    cout << endl;
    //cout << ver(a) << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int N, C;
int s[100000], t[100000], c[100000];
int sm[200002];
int tt[200002];

int main(void) {
    cin >> N >> C;
    for (int i = 0; i < N; ++i) {
        cin >> s[i] >> t[i] >> c[i];
    }

    for (int i = 1; i <= C; ++i) {
        for (int j = 0; j < 200002; ++j) {
            tt[j] = 0;
        }
        for (int j = 0; j < N; ++j) {
            if (c[j] == i) {
                tt[s[j] * 2 - 1]++, tt[t[j] * 2]--;
            }
        }
        for (int j = 1; j <= 200002; ++j) {
            tt[j] += tt[j - 1];
        }
        for (int j = 0; j < 200002; ++j) {
            if (tt[j] > 0) {
                sm[j]++;
            }
        }
    }

    int mx = 0;
    for (int j = 0; j < 200002; ++j) {
        if (mx < sm[j]) {
            mx = sm[j];
        }
    }

    cout << mx << endl;
    return 0;
}

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

using namespace std;

#define all(x) (x).begin(), (x).end()

typedef long long ll;

const ll INF = 1e18;

const int N = 1e5 + 10, LOG = 18;
ll a[N], dp[N], ndp[N];
int n, m, K;

void solve() {
  cin >> n >> m >> K;
  for (int i = 1; i <= n; i++) {
    cin >> a[i]; dp[i] = a[i];
  }
  for (int k = 2; k <= K; k++) {
    ndp[1] = -INF;
    deque<ll> q; q.push_back(dp[1]);
    for (int i = 2; i <= n; i++) {
      int l = max(1, i - m), r = i - 1;
      ll upd = q.front();
      ndp[i] = upd + k * 1LL * a[i];
      while (!q.empty() && q.back() < dp[i])
        q.pop_back();
      q.push_back(dp[i]);
      if (1 <= i - m && !q.empty() && q.front() == dp[i - m])
        q.pop_front();
    }
    for (int i = 1; i <= n; i++) {
      dp[i] = ndp[i];
    }
  }
  cout << *max_element(dp + 1, dp + 1 + n);
}

// CHECK LIMITS (n <= 10^5)
// CHECK CORNER CASES (n == 1)

int main() {
  ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
  cout.setf(ios::fixed), cout.precision(20);
  //cout << 1.0 * clock() / CLOCKS_PER_SEC << endl;
  solve();
}


Measured memory_bytes: 6008
#include <iostream>
#include <string>
using namespace std;

struct Team{
  int team_num,time,correct;
};

int main(){
  Team data[51];
  while(1){
    int i,j,T,P,R; cin >> T >> P >> R;
    if ( T == 0 && P == 0 && R == 0 ) break;
    for( i = 1; i <= T; i++ ){
      data[i].time = 0;
      data[i].correct = 0;
      data[i].team_num = i;
      /* i???????????????????????????????????????????????????*/
    }

    int t,p,jikan,twrong[51][11];
    for( i = 0; i < 51; i++ ){
      for( j = 0; j < 11; j++ ){
	twrong[i][j]=0;
      }
    }
    string str;
    for( i = 0; i < R; i++ ){
      cin >> t >> p >> jikan >> str;
      if( str == "CORRECT" ){
	data[t].correct++;
	data[t].time = data[t].time + twrong[t][p] * 1200 + jikan;
      }else if( str == "WRONG" ){
	twrong[t][p]++;
      }
    }
    /* for( i = 0; i < T; i++ ){
      for( j = 1; j < T; j++ ){
	if( data[j].team_num > data[j+1].team_num ) 
	  swap( data[j],data[j+1] );
      }
      }*/

    for( i = 0; i < T; i++ ){
      for( j = 1; j < T; j++ ){
	if( data[j].time > data[j+1].time ) 
	  swap( data[j],data[j+1] );
      }
    }

    for( i = 0; i < T; i++ ){
      for( j = 1; j < T; j++ ){
	if( data[j].correct < data[j+1].correct ) 
	  swap( data[j],data[j+1] );
      }
    }

    for( i = 1; i <= T; i++ ){
      cout << data[i].team_num << " "
	   << data[i].correct << " " << data[i].time << endl;
    }
    
  }
  return 0;
}

Measured memory_bytes: 1216
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <bitset>

bool IsHeisei(int y, int m, int d) {
  if(y < 2019) return true;
  if(y == 2019 && m < 4) return true;
  if(y == 2019 && m == 4 && d <= 30) return true;
  return false;
}

int main() {
  int N;
  double sum = 0;
  scanf("%d", &N);
  for(int i = 0; i < N; i++){
    double q;
    char s[8];
  	scanf("%lf", &q);
    scanf(" %s", s);
    if(s[0] == 'J'){
      sum += q;
    } else{
      sum += q * 380000;
    }
  }
  printf("%lf\n", sum);
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<LL,LL>
#define x first
#define y second
#define pi acos(-1)
#define sqr(x) ((x)*(x))
#define pdd pair<double,double>
#define MEMS(x) memset(x,-1,sizeof(x))
#define MEM(x) memset(x,0,sizeof(x))
#define less Less
#define EPS 1e-4
#define arg ARG
#define cpdd const pdd
#define rank Rank
#define KK 500
#define MXN 200005
int main(){
    int n,a,b;
    while(scanf("%d %d %d",&n,&a,&b)!=EOF){
        int now=0;
        int ans=0;
        for(int i = 1;i<=n;i++){
            if(i%10000==0){
                now-=36;
            }
            else if(i%1000==0){
                now-=27;
            }
            else if(i%100==0){
                now-=18;
            }
            else if(i%10==0){
                now-=9;
            }
            now++;
            if(now>=a&&now<=b){
                ans+=i;
            }
        }
        printf("%d\n",ans);
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000007;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N, k;
	cin >> N >> k;

	vector<Int> x(N);
	Int flag = 1;
	for (Int i = 0; i < N; i++) {
		cin >> x[i];
		//if (x[i] == 0) k--;
	}
	
	Int ans = INF;
	Int temp = 0;
	//if (k) {
		for (Int i = 0; i <= N-k; i++) {
			temp = abs(0 - x[i]) + abs(x[k + i - 1] - x[i]);
			ans = min(ans, temp);
		}

		for (Int i = 0; i <= N-k; i++) {
			temp = abs(0 - x[k+i-1]) + abs(x[k + i - 1] - x[i]);
			ans = min(ans, temp);
		}
	/*}
	else {
		ans = 0;
	}
	*/

	cout << ans << endl;


}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
	int N;
	cin >> N;
	int a, max = -1000001, min = 1000001;
	long long sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> a;
		if (a > max) max = a;
		if (a < min)min = a;
		sum += a;
	}
	cout << min << ' ' << max << ' ' << sum << endl;
}


Measured memory_bytes: 3104
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#define my_abs(x) ((x) < 0 ? -(x) : (x))
#define pb push_back
typedef long long ll; 
std::vector<std::pair<int, int> > adj[100005], rev[100005]; 
ll X[100005], Y[100005], ans[100005];
int n, m, s, t; 
template <typename T>
inline void dij(T &g, int st, ll *dis)
{
	std::priority_queue<std::pair<ll, int> > que; 
	memset(dis, 0x3f, n << 3); 
	dis[st] = 0; 
	que.push({0, st}); 
	while (!que.empty())
	{
		int u = que.top().second; 
		ll d = -que.top().first; 
		que.pop(); 
		if (dis[u] != d)
			continue; 
		for (auto &e : g[u])
		{
			if (dis[e.first] > dis[u] + e.second)
			{
				dis[e.first] = dis[u] + e.second; 
				que.push({-dis[e.first], e.first}); 
			}
		}
	}
}
int main()
{
	// freopen("D.in", "r", stdin); 
	scanf("%d%d%d%d", &n, &m, &s, &t);
	for (int i = 0; i < m; i++)
	{
		int u, v, a, b; 
		scanf("%d%d%d%d", &u, &v, &a, &b); 
		adj[--u].pb({--v, a}); 
		adj[v].pb({u, a}); 
		rev[u].pb({v, b}); 
		rev[v].pb({u, b}); 
	}
	dij(adj, --s, X); 
	dij(rev, --t, Y);
	for (int i = n - 1; i >= 0; i--)
		ans[i] = std::max(ans[i + 1], (ll)1e15 - X[i] - Y[i]); 
	for (int i = 0; i < n; i++)
		printf("%lld\n", ans[i]);
	return 0; 
}


Measured memory_bytes: 16252
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<int>;
const int maxn = 305, mlg = 18, rt = 1<<10, mod = 1e9 + 7;
int good[maxn][maxn][maxn], dp[maxn][maxn][maxn], n, m;
vector<pair<int, int>> a;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	int al = 1<<30, ar = 0, bl = 1<<30, br = 0;
	for(int x, y, i = 0; i < n; i++) {
		cin >> x >> y;
		if(x < y) swap(x, y);
		al = min(x, al);
		ar = max(x, ar);
		bl = min(y, bl);
		br = max(y, br);
		a.pb({x, i});
		a.pb({y, i});
	}
	//cout << al << " " << ar << " " << bl << " " << br << '\n';
	ll ans = (ar-al) * 1ll * (br-bl);
	sort(all(a));
	al = min(al, bl), ar = max(br, ar);
	map<int, int> cnt;
	//for(auto i : a) cout << i.first << " - " << i.second << '\n';
	for(int i = 0, j = 0; i+1 < a.size(); i++) {
		cnt[a[i].second]++;
		while(cnt[a[j].second]>1) cnt[a[j++].second]--;
		//cout << j << " " << i << '\n';
		if(cnt.size() == n && j > 0) ans = min(ans, (ar - al) * 1ll * (a[i].first - a[j].first));
	}
	cout << ans;
}


Measured memory_bytes: 15084
//g++ -std=gnu++14 a.cpp

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <random>
#include <math.h>
//#include <ostream>


using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;

/*
int all = (N-1) - (Y-X) + 1;

for(int i = 1;i < N;i++){

  if(i <= Y-X){
    int ans = 0;
    ans += (all+1) - i;
    for(int j = X+1;j <= Y;j++){
      if(j - i >= 1)ans++;
    }
    ans = max(ans,0);
    cout << ans << endl;
    continue;
  }

  cout << max(all+1-i,0) << endl;
}*/

int main(){
  int N,X,Y;
  cin >> N >> X >> Y;
  vector<vector<int>> d(2010,vector<int>(2010,INF));

  for(int i = 1;i < N;i++){
    for(int j = i+1;j <= N;j++){
      if(i <= X && j <= X){
        d[i][j] = min(j-i,d[i][j]);
      }else if(i >= Y && j >= Y){
        d[i][j] = min(j-i,d[i][j]);
      }else if(i <= X && j >= Y){
        d[i][j] = min(j-Y+1+X-i,d[i][j]);
      }else if(i > X && j < Y){
        d[i][j] = min(j-i,Y-j+i-X+1);
      }else if(i <= X && j < Y){
        d[i][j] = min(j-i,X-i+Y-j+1);
      }else{
        d[i][j] = min(j-i,j-Y+i-X+1);
      }
    }
  }

  vector<int> cnt(2010,0);
  for(int i = 1;i < N;i++){
    for(int j = i+1;j <= N;j++){
      cnt[d[i][j]]++;
    }
  }

  for(int i = 1;i < N;i++){
    cout << cnt[i] << endl;
  }

}


Measured memory_bytes: 16128
/*
    Author : Nishant Gupta 2.0
*/
#include<bits/stdc++.h>
using namespace std;

#define LL long long int
#define getcx getchar_unlocked
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define MAX 100005
#define LOG_MAX 20
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL (LL(1e18))
#define chk(a) cerr << endl << #a << " : " << a << endl
#define chk2(a,b) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << endl
#define chk3(a,b,c) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << endl
#define chk4(a,b,c,d) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << "\t" << #d << " : " << d << endl
#define rep(i, a, n) for(i=a;i<n;i++)
#define rev(i, a, n) for(i=a;i>=n;i--)
#define in(x) scanf("%d", &x)
#define inl(x) scanf("%lld", &x)
#define in2(x, y) scanf("%d %d", &x, &y)
#define inl2(x, y) scanf("%lld %lld", &x, &y)
#define MSV(A,a) memset(A, a, sizeof(A))
#define rep_itr(itr, c) for(itr = (c).begin(); itr != (c).end(); itr++)
#define finish(x) {cout<<x<<'\n'; return;}
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;
const char en = '\n';

void solve() {
	int n;
	in(n);
	LL a[n];
	LL sum = 0;
	LL f[MAX] = {0};
	for(int i=0;i<n;i++) {
		inl(a[i]);
		f[a[i]]++;
		sum+=a[i];
	}
	
	int q;in(q);
	while(q--) {
		int b, c;
		in2(b, c);
		
		sum -= (f[b]*b);
		sum += (f[b]*c);
		f[c] += f[b];
		f[b] = 0;
		cout<<sum<<en;
	}
	
}

int main() {
	int t = 1;
	
	//~cin>>t;
	while(t--) {
		solve();
	}
    return 0;
}


Measured memory_bytes: 5216
#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#define int long long
using namespace std;
const int INF=3e5+5;
struct _node_data {int x,y;} aa[INF],bb[INF];
int h,w,m,cntx[INF],cnty[INF],ans;
map <int,map <int,bool> > Map;
bool cmp1(_node_data xx,_node_data yy) {
        return xx.x>yy.x;
}
int fzx_max(int x,int y) {
        return x<y ? y : x;
}
signed main()
{
        scanf("%lld %lld %lld",&h,&w,&m);
        for (int i=1; i<=m; i++) {
                int x=0,y=0; scanf("%lld %lld",&x,&y);
                Map[x][y]=1; cntx[x]++; cnty[y]++;
        }
        for (int i=1; i<=h; i++) {aa[i].x=cntx[i]; aa[i].y=i;}
        for (int i=1; i<=w; i++) {bb[i].x=cnty[i]; bb[i].y=i;}
        sort(aa+1,aa+1+h,cmp1); sort(bb+1,bb+1+w,cmp1);
        for (int i=1; i<=h; i++)
                for (int j=1; j<=w; j++) {
                        if (aa[i].x+bb[j].x<=ans) break;
                        ans=fzx_max(ans,aa[i].x+bb[j].x-Map[aa[i].y][bb[j].y]);
                }
        cout<<ans<<"\n";
        return 0;
}


Measured memory_bytes: 64752
#include <bits/stdc++.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

typedef long long int lli;
typedef pair<int, int> ii;

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;}

#ifdef LOCAL
    #define eprintf(...) printf(__VA_ARGS__)
#else
    #define eprintf(...) 1
#endif

#define ROUNDUP(a, b)         ( ((a) + ((b) - 1) ) / (b))
#define SET_ZERO(a)             ( memset((a), 0, sizeof(a)))
#define SET_NUM_ARRAY(a,b)    ( memset((a), b, sizeof(a)))

int main() {
    int N;
    int x[109], y[109], h[109];
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i] >> h[i];
    }

    int H;
    int cx = 0, cy = 0;
    for (int cccx = 0; cccx <= 100; cccx++) {
        for (int cccy = 0; cccy <= 100; cccy++) {
            int complete = 1;
            int hypH;
            queue<ii> outque;
            for (int first = 1, i = 0; i < N; i++) {
                if (h[i] != 0) {
                    if (first == 1) {
                        first = 0;
                        hypH = abs(x[i] - cccx) + abs(y[i] - cccy) + h[i];
                    } else {
                        if (hypH != abs(x[i] - cccx) + abs(y[i] - cccy) + h[i]) {
                            complete = -1;
                            break;
                        }
                    }
                } else {
                    outque.push(ii(x[i], y[i]));
                }
            }
            while (!outque.empty()) {
                ii ip = outque.front(); outque.pop();
                int ix = ip.first;
                int iy = ip.second;
                if (hypH - abs(ix - cccx) - abs(iy - cccy) > 0) complete = -1;
            }
            if (complete == 1) {
                cx = cccx;
                cy = cccy;
                H = hypH;
            }
        }
    }
    cout << cx << " " << cy << " " << H << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<limits>
#include<algorithm>
#include<numeric>
#include<utility>

int main(){
    std::string s, S;
    std::cin >> s;

    unsigned long long int A_stock=0;
    unsigned long long int cnt=0;

    for(int i=0;i<s.size();i++){
        if(s[i]=='A'){
            A_stock++;
        }else if(s[i]=='B'){
            if(i+1!=s.size() && s[i+1]=='C'){
                cnt+=A_stock;
                i++;
            }else{
                A_stock=0;
            }
        }else if(s[i]=='C'){
            A_stock=0;
        }
    }

    std::cout << cnt << std::endl;

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 25;
const int MOD = 1e9+7;
// union by size + path having
class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

int main() {
	int n,m;
	cin >> n >> m;
	vector<vector<int>> g(n);
	rep(i, m) {
			int a, b; cin >> a >> b;
			g[a-1].push_back(b-1);
	}
	UnionFind uf(n);
	rep(i,n) {
		for (int to : g[i]) {
			uf.merge(i,to);
		}
	}
	int ans = 1;
	rep(i,n) {
		int now = uf.size(i);
		ans = max(ans, now);
	}
	cout << ans << endl;
}

Measured memory_bytes: 17244
#include <iostream>

int main(){
	int a,b,k;
	std::cin>>a>>b>>k;
	int c=b-a+1;
	if(c<k*2||c<k){
		for(int x=a;x<=b;x++){
			std::cout<<x<<std::endl;
		}
	}
	else{
		for(int x=a;x<k+a;x++){
			std::cout<<x<<std::endl;
		}
		for(int x=b-k+1;x<=b;x++){
			std::cout<<x<<std::endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

signed main(){
    int n;
    cin >> n;
    ll h[n];
    REP(i,n){
        cin >> h[i];
    }
    ll mx = 0;
    REP(i,n){
        mx = max(mx, h[i]);
        if(mx - h[i] > 1){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 1024
s=[0,1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342, 111528, 120141, 128047, 134580, 146316, 154177, 164817, 174438, 185836, 194157, 207927, 218812, 233268, 245277, 257857, 268182, 288216, 299257, 313635, 330204, 347836, 362973, 383709, 397042, 416448, 434025, 456967, 471948, 499740, 515581, 536073, 559758, 583960, 604833, 633651, 652216, 683712, 709065, 734233, 754734, 793188, 818917, 846603, 874512, 909496, 933081, 977145, 1006126, 1041504, 1073385, 1106467, 1138536, 1187112, 1215145, 1255101, 1295142, 1342852, 1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772, 10813692]
print(s[int(input())])

Measured memory_bytes: 9332
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <stack>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef unsigned long long int ll;

void printBit(int num){
	if(num == 0){
		cout<<0;
		return;
	}
	while(num > 0){
		if(num % 2 == 1){
			cout<<1;
		}else{
			cout<<0;
		}
		num /= 2;
	}
	return;
}

int main()
{
	int d,g;
	cin>>d>>g;
	vector<int> p(d);
	vector<int> c(d);
	rep(i,d) cin>>p[i]>>c[i];
	int ans = 1000;
	for(int bit = 0;bit < (1<<d); bit++){
		vector<int> tempP(d);
		int localSum = 0;
		int localCost = 0;
		for(int i = 0; i < d; i++){
			if( bit & (1<<i)){
				localCost += p[i];
				localSum += p[i] * (100*(i+1)) + c[i];
				tempP[i] = 0;
			}else{
				tempP[i] = max(0,p[i]-1);
			}
		}
		for(int i = d-1; i >= 0; i--){
			if( localSum >= g){
				ans = min(ans,localCost);
				break;
			}
			if( localSum + 100*(i+1)*tempP[i] >= g){
				for(int j = 0; j < tempP[i]; j++){
					localSum += (i+1)*100;
					localCost++;
					if(localSum >= g) break;
				}
				ans = min(ans,localCost);
				break;
			}else{
				localSum += tempP[i] * (100*(i+1));
				localCost += tempP[i];
			}
		}
		if(localSum >= g) ans = min(ans,localCost);
		//printBit(bit);
		//cout<<":"<<localSum<<","<<localCost<<endl;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3168
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<vi> vivi;
typedef vector<ll> vll;
typedef vector<vll> vllvll;
typedef pair<int, int> P;
typedef queue<P> QP;
using Graph = vector<vector<int>>;
const int INF = 1001001001;
const int mINF = -1001001001;
const int mod = 1000000007;
// 小数点　<< fixed << setprecision(0) <<
// sort降順　sort(ALL(),greater<int>());
// 文字判定　isupper islower
// 順列　do {} while(next_permutation(ALL(X)));
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};
typedef struct edge se;
typedef vector<edge> ve;

int main() {
  int n,sum=0;
  cin >> n;
  vi a(n);
  REP(i,n) {
    cin >>a[i];
    sum+=a[i];
  }
  bitset<4000001> dp;
  dp[0]=1;
  REP(i,n) {
    dp|=(dp<<a[i]);
  }
  for(int i=(sum+1)/2;i<=sum;i++) {
    if(dp[i]==1) {
      cout << i << endl;
      break;
    }
  }


  return 0;
}


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

int main() {
  int n,q;
  cin>>n>>q;
  string s;
  cin>>s;
  vector<int> v(n);
  char c='u';
  int cnt=0;
  rep(i,n){
    if (c!='A'){
      c=s[i];
      v[i]=cnt;
      continue;
    }
    else{
      if (s[i]=='C'){
        cnt++;
        v[i]=cnt;
        c=s[i];
      }
      else{v[i]=cnt;c=s[i];}
    }
  }
  rep(i,q){
    int l,r;
    cin>>l>>r;
    int ans=v[r-1]-v[l-1];
    cout<<ans<<endl;
  }



  }


Measured memory_bytes: 1408
#define DEBUG
#include <bits/stdc++.h>
#include <ext/numeric>
using namespace std; using __gnu_cxx::power;
using ll = long long; using ull = unsigned long long; using ld = long double;
const ll llinf = (1ll<<61)-1; const double eps = 1e-6, ldeps = 1e-9;
#define all(x) begin(x), end(x)
#define sl(a) int(strlen(a))
#define sz(a) int(a.size())
#define TCC template<class C
struct Dbg { static constexpr auto &os = cout;   // replace by cerr in interactive.
#define ENI typename enable_if<
#define DTOR , Dbg&>::type operator<<
#define RIS return *this
TCC> static auto o(C *x)->decltype(os << *x, 0);
TCC> static char o(...);
TCC> ENI sizeof o<C>(0)!=1 DTOR(const C &x) {os<<x; RIS;}
TCC> Dbg &dump(C b, C e) {
    int ii = 0;
    for(C i = (os << "\n[", b); i!=e and ii<26; i++, ii++) *this << ", "+2*(i==b) << *i;
    RIS << ']';
}
TCC> ENI sizeof o<C>(0)==1 DTOR(const C &x) {
    return dump(all(x));
}
TCC, size_t X> ENI !is_same<C, const char>::value DTOR(C (&x)[X]) {
    return dump(all(x));
}
TCC, class D> Dbg &operator<<(const pair<C, D> &x) {RIS<<'{'<<x.first<<", "<<x.second<<'}';}
Dbg &operator<<(ostream&(*x)(ostream&)) { os << x; RIS; }
} dbg;
void err(istringstream *iss) { delete iss; }
TCC, class... Args> void err(istringstream *iss, const C &val, const Args &... args) {
    string name; *iss >> name; if (name.back()==',') name.pop_back();
    dbg << name << " = " << val << "; ", err(iss, args...);
}
#ifdef DEBUG
#define bug(args...) dbg << __LINE__ << ": ", err(new istringstream(#args), args), dbg << endl
#else
#define bug(args...) 0
#endif
#define ASSERT(a, o, b, args...) if (!((a)o(b))) bug(a, b, ##args), assert((a)o(b));
int T = 1, Q, cn;
const int inf = 1000000007, mxn = -1;

ll x,K,d;

signed main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); cout.precision(11), cout.setf(ios::fixed);
    // cin >> T;
    auto inputAll = [&]()->void {
        
    };
    auto kase = [&]()->void {
        // cout << "Case " << cn << ": ";
        cin>>x>>K>>d;
        x=abs(x);
        ll moves=x/d;
        if(moves>K)return cout<<x-K*d<<'\n',void();
        x-=moves*d;
        cout<<(((K-moves)&1) ? abs(x-d) : x)<<'\n';
    };
    auto resetAll = [&]()->void {
        
    };
    while (cn++!=T) inputAll(), kase(), resetAll();
}


Measured memory_bytes: 3624
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
t = []
for i in range(x):
    for j in range(y):
        for l in range(z):
            if (i+1) * (j+1) * (l+1) <= k:
                t.append(a[i]+b[j]+c[l])
            else:
                break
t.sort(reverse=True)
for i in range(k):
    print(t[i])

Measured memory_bytes: 8708
/*
for (int i = 0; i < N; ++i){}

// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/
typedef long long ll;
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>

using namespace std;
 
int main() {
	// 入力
    string S;
    int w;
    cin >> S >> w;
    
    
    int n;
    if (S.size()%w==0) n = S.size()/w;
    else n = S.size()/w+1;
    
    string ans = "";
    for (int i = 0; i < n; ++i) {
    	ans += S.substr(i*w,1);
    }
    //出力
    cout << ans << endl;
	// printf("%d\n", 4);	// 3
}
 


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

int gcd(int a, int b) {
    int remain = max(a, b) % min(a, b);
    if (remain == 0) return min(a, b);
    else return gcd(min(a,b), remain);
}

int main() {
    int n;
    cin >> n;
    int x0,x1,x;
    cin >> x0 >> x1;
    int g = gcd(x0, x1);
    for (int i = 0; i < n - 2; i++) {
        cin >> x;
        g = gcd(g, x);
    }
    cout << g << endl;
}


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

int n, m, s, l, p, w;
int memo[400] = {0};
int dp[400][400] = {0};
int ans[400] = {0};
bool able = 1;

int main() {
  int i, j, k;
  cin >> n;
  for(i = 0; i <= 393; ++i) memo[i] = -1;

  for(i = 0; i < n; ++i) {
    cin >> s >> l >> p;
    for(j = s; j <= l; ++j) memo[j] = max(memo[j], p);
  }
  cin >> m;
  for(k = 0; k < m; ++k) {
    cin >> w;
    for(i = 1; i <= 393; ++i) {
      for(j = 0; j <= w; ++j) {
        dp[i][j] = dp[i - 1][j];
        if(i <= j)
          dp[i][j] = max(dp[i][j], dp[i][j - i] + memo[i]);
      }
    }
    if(dp[393][w] == 0) {
      able = 0;
      break;
    }
    else
      ans[k] = dp[393][w];
  }
  if(able)
    for(i = 0; i < m; ++i) cout << ans[i] << endl;
  else
    cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 3712
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] a = new int[n];
    for(int i = 0; i < n; i++) {
      a[i] = sc.nextInt();
    }
    int count = 0;
    for(int i = 0; i < n - 1; i++) {
      boolean sort = false;
      int min = a[i];
      int key = i;
      for(int j = i; j < n; j++) {
        if(min > a[j]) {
          min = a[j];
          key = j;
          sort = true;
        }
      }
      if(sort) {
        a[key] = a[i];
        a[i] = min;
        count++;
      }
    }
    for(int i = 0; i < n; i++) {
      if(i == n- 1) {
        System.out.println(a[i]);
      } else {
        System.out.print(a[i] + " ");
      }
    }
    System.out.println(count);
  }
}



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

using namespace std;

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

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}
bool check(const vector<vector<ll>>& color, const ll d) {
    const ll h = color.size();
    const ll w = color[0].size();
    rep(y1, h) rep(x1, w) rep(y2, h) rep(x2, w) {
        if (abs(x2 - x1) + abs(y2 - y1) == d) {
            if (color[y1][x1] == color[y2][x2]) return false;
        }
    }
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll w, h, d; cin >> h >> w >> d;
    ll L = (w + h - 1);
    ll D = d;
    vector<vector<ll>> color{
        {0, 1},
        {2, 3},
    };
    vector<vector<ll>> m(L, vector<ll>(L));
    rep(y, L) rep(x, L) {
        ll yb = y / D;
        ll xb = x / D;
        m[y][x] = color[yb % 2][xb % 2];
    }
    // cout << m << endl;
    vector<vector<ll>> ans(h, vector<ll>(w));
    rep(y, h) rep(x, w) {
        ans[y][x] = m[x + y][x - y + h - 1];
    }
    const string S = "RYGB";
    rep(y, h) {
        rep(x, w) {
            cout << S[ans[y][x]];
        }
        cout << endl;
    }
    // assert( check(ans, d) );
}


Measured memory_bytes: 10368
#define lp(i,n) for(int i=0;i<n;i++)
#define pau system("pause")
typedef long long ll;
using namespace std;
#include<bits/stdc++.h>

map<ll,int> prime(ll n){
    map<ll,int>res;
    for(ll i=2;i*i<=n;++i){
        while(n%i==0){
            res[i]++;
            n/=i;
        }
    }
    if(n!=1)
        res[n]=1;
    return res;
}

int main(){
    ll n;
    cin>>n;

    map<ll,int> m=prime(n);
    vector<int> s(50);
    int now=1,cnt=0;
    for(int i=1;i<50;++i){
        s[i]=now;
        ++cnt;

        if(now==cnt-1){
            now++;
            cnt=0;
        }
    }
    int ans=0;
    for(auto &p:m){
        ans+=s[p.second];
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3640
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int[] l = new int[8];
            for (int i = 0; i < 8; i++) {
                l[i] = sc.nextInt();
            }
            int v = 0;
            int min = Integer.MAX_VALUE;
            int[] c = { 1, 2, 1, 2, 1, 4, 1, 4 };
            int[] o = { 0, 2, 6, 4, 1, 3, 7, 5 };
            for (int i = 0; i < 8; i++) {
                int sum = 0;
                for (int j = 0; j < 8; j++) {
                    sum += Math.max(0, c[(o[i] + j) % 8] - l[j]);
                }
                if (min > sum) {
                    min = sum;
                    v = o[i];
                }
            }
            for (int i = 0; i < 8; i++) {
                System.out.print(c[(i + v) % 8] + (i != 7 ? " " : "\n"));
            }
        }
    }
}


Measured memory_bytes: 29832
import sys


def read():
    return sys.stdin.readline()


def main():
    n = int(read())
    d = [0] * n
    present = [[] for i in range(n)]
    for i in range(n - 1):
        u, v = sorted(map(lambda x: int(x) - 1, read().split()))
        d[v] += 1
        present[u].append(v)
    ans, cur = 0, 0
    for v in range(n):
        cur += (n - v) * d[v]
    for L in range(n):
        ans += (L + 1) * (L + 2) // 2 - cur
        for v in present[L]:
            cur -= (n - v)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 37608
#include <bits/stdc++.h>
using namespace std;
int n,a[101],sum=0;
int main() {
    cin>>n;
    for (int i = 1; i <= n; ++i) {
        cin>>a[i];
        if(i%2&&a[i]%2)sum++;
    }
    cout<<sum;
}

Measured memory_bytes: 3592
package main

import "fmt"

func main() {
	var K, sum int
	fmt.Scan(&K)
	w := make([][]int, K+1)
	for i := 0; i < len(w); i++ {
		w[i] = make([]int, K+1)
		for j := 0; j < len(w[i]); j++ {
			w[i][j] = gcd(i, j)
		}
	}
	for a := 1; a <= K; a++ {
		for b := 1; b <= K; b++ {
			for c := 1; c <= K; c++ {
				sum += w[w[a][b]][c]
			}
		}
	}
	fmt.Println(sum)
}
func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}


Measured memory_bytes: 2148
#include<bits/stdc++.h>
using namespace std;
map<int,int>mp; 
int ans=1e9,ret;
int main(){
	int n,X;
	cin>>X>>n;
	for(int i=1;i<=n;i++){
		int x;cin>>x;mp[x]=114514;
	}
	for(int i=-200;i<=200;i++){
		if(mp[i]<1919 && abs(i-X)<ans)ans=abs(i-X),ret=i; 
	}
	cout<<ret;
}

Measured memory_bytes: 3660
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <iomanip>
using namespace std;

typedef long long ll;

ll srch_around(vector <vector <char> > tile, int h, int w){
    if(tile[h][w+1]=='#' || tile[h][w-1]=='#' || tile[h+1][w]=='#' || tile[h-1][w]=='#') return 1;
    else return 0;
}

int main()
{
    int H,W;
    cin >> H >> W;
    vector < vector <char> > tile(H+2, vector<char>(W+2, '.'));
    for(int i=1; i<=H; i++){
        for(int j=1; j<=W; j++){
            cin >> tile[i][j];
        }
    }
    bool flag=true;
    for(int i=1; i<=H; i++){
        for(int j=1; j<=W; j++){
            if(tile[i][j]=='.') continue;
            if(srch_around(tile, i, j)==0) flag=false;
        }
    }
    
    if(flag) cout << "Yes";
    else cout << "No";
    



    return 0;
}


Measured memory_bytes: 256