akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>    
using namespace std;
 
#define CIN1(a) long long a;cin >> a;
#define CIN2(a,b) long long a,b;cin >> a >> b;
#define CIN3(a,b,c) long long a,b,c;cin >> a >> b >> c;
#define rep(i,n) for(int i=0,i##_len=(n); i<i##_len; ++i)
 
int main(){
    string s;cin >> s;
    int ans;
    for(int i=0;i+3<=s.size();i++){
        int tmp = abs(753-stoi(s.substr(i,3)));
        if(!i) ans = tmp;
        else ans = min(ans,tmp);
    }
    cout << ans << endl;
}


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

int main() {

  while( true ) {

    long long int n, q;
    cin >> n >> q;
    if ( n == 0 ) break;

    long long int cnt[101] = {};
    long long int num = 0;

    for ( long long int i = 0; i < n; i++ ) {

      long long int m;
      cin >> m;

      for ( long long int j = 0; j < m; j++ ) {

	long long int in;
	cin >> in;
	cnt[in]++;
	num = max( num, cnt[in] );

      }

    }

    if ( q > num ) {
      cout << 0 << endl;
    }else {

      for ( long long int i = 1; i <= 100; i++ ) {

	if ( cnt[i] == num ) {
	  cout << i << endl;
	  break;
	}

      }

    }

  }

  return 0;

}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds;

#define pbds tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ll long long
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define ii pair<int,int>
#define vii vector<ii>
#define vi vector<int>

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)
 
// debug templates 
#define debug(x)       cerr<< #x <<" : "<< x << endl;
#define debuga(A,N)    cerr<< #A <<" : [";for(int i = 0; i<N;i++) cerr<<A[i]<<" "; cerr<<"]\n";
#define debuga2(A,N,M) cerr<< #A << " : \n"; for(int i=0;i<N;i++){cerr<<"[";for(int j=0;j<M;++j) cerr<<A[i][j]<<" ";cerr<<"]\n";}
#define debugp(p)      cerr<< #p <<" : "<<"("<<(p).first<<","<<(p).second<<")\n";
#define debugv(v)      cerr<< #v <<" : "<<"[";for(int i = 0; i< (v).size(); i++) cerr<<v[i]<<" "; cerr<<"]\n";
#define debugv2(v)     cerr<< #v << " : \n"; for(int i=0;i<v.size();i++){cerr<<"[";for(int j=0;j<(v[0].size());++j) cerr<<v[i][j]<<" ";cerr<<"]\n";}
#define debugs(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin(); itr!=m.end();itr++) cerr<<*itr<<" "; cerr<<"]\n";
#define debugm(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin();itr!=m.end(); itr++) cerr<<"("<<itr->first<<","<<itr->second<<") ";cerr<<"]\n";
 

void solve(){
    int n,x; cin >> n >> x;
    int l[n+1];
    FOR(i,1,n+1) cin >> l[i];
    l[0] = 0;
    FOR(i,1,n+1) l[i] += l[i-1];
    int cnt = 0;
    FOR(n+1){
        if(l[i] <= x) ++cnt;
        else break;
    }
    cout << cnt;
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	solve();
	return 0;
}
 


Measured memory_bytes: 3600
#include<iostream>
#include<iomanip>
#include<stack>
#include<queue>
#include<numeric>
#include<algorithm>
#include<string>
#include<map>
#include<bitset>
#include<set>
#include<cmath>
#define int long long
#define inf 1145141919ll
#define oku 1000000007ll
using namespace std;
int a,b,c,d,e,f,g,n,ans;
int dx[]={0,-1,0,1,0};
int i,j,k;
struct A{

};
int p[100000],q[100000];
signed main(){
	cin>>n;
	for(i=0;i<n;i++){
		cin>>p[i]>>q[i];
	}
	for(i=n-1;i>=0;i--){
		p[i]+=ans;
		ans+=(q[i]-(p[i]%q[i]))%q[i];
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define endl              "\n"
#define fast               ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int main()
{
    fast;
    long long   i,j,n,c=0,d=0,e=0,f=0,g=0,h=0,k,r;
    cin>>n>>r;
    if(n>=10)
    {
        cout<<r;
    }
    else
    {
        c=100*(10-n);
        cout<<r+c;
    }
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
  int i, j, k, h, w, n, nowx = 0, nowy = 0, a;
  scanf("%d%d%d", &h, &w, &n);
  int s[h][w];
  for(i = 0; i < n; ++i) {
    scanf("%d", &a);
    for(j = 0; j < a; ++j) {
      s[nowy][nowx] = i + 1;
      if((nowx == w - 1 && !(nowy % 2)) || (!nowx && nowy % 2)) nowy++;
      else if(nowy % 2) nowx--;
      else nowx++;
    }
  }
  for(i = 0; i < h; ++i) {
    for(j = 0; j < w; ++j) printf("%d ", s[i][j]);
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    long long money, happy = 0;
    cin >> money;
    long long coin500 = money / 500;
    happy += coin500 * 1000;
    money -= 500 * coin500;
    happy += 5 * (money / 5);
    cout << happy << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double dp[3000][3000];
double p[3000];ll n;
double solve(ll i,ll j)
{
	if(dp[i][j]!=-1)
	return dp[i][j];
	if(i<j)
	return 0;
	if(i==0 && j==0)return 1;
	if(j==0)return solve(i-1,j)*(1-p[i]);
	dp[i][j]=solve(i-1,j-1)*p[i] + solve(i-1,j)*(1-p[i]);
	return dp[i][j];
}
int main() {
	cout<<fixed;
	for(int i=0;i<3000;i++)
	for(int j=0;j<3000;j++)
	dp[i][j]=-1;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>p[i];
	double d=0;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++){
		dp[i][j]=solve(i,j);
		}
	}
	for(int j=n;j>n/2;j--)
	d+=dp[n][j];
	cout<<setprecision(16)<<d;
}

Measured memory_bytes: 70528
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
     
     
#define fs first
#define sc second
     
using namespace std;
     
     
typedef long long ll;
typedef pair<ll, ll> P;
     
     
int main(){
  ll N, K;

  cin >> N;
  cin >> K;

  ll arr[N];
  for(int i = 0; i < N; i++){
    cin >> arr[i];
  }

#ifdef DEBUG
  cout << K << endl;
#endif

  ll tmpmax = 0;
  for(ll i = 0; i <= K; i++){
    for(ll j = 0; j <= K - i; j++){
      vector<ll> negList;
      ll tmpval = 0;
      
      ll lmax = min(j, N);
      ll rmax = min(K - i - j, N - lmax);

#ifdef DEBUG
      cout << "i=" << i << ", ";
      cout << "lmax=" << lmax << ", ";
      cout << "rmax=" << rmax << endl;
#endif
      
      for(ll ii = 0; ii < lmax; ii++){
	tmpval += arr[ii];
	if(arr[ii] < 0) negList.emplace_back(arr[ii]);
      }
      for(ll jj = 0; jj < rmax; jj++){
	tmpval += arr[N-1-jj];
	if(arr[N-1-jj] < 0) negList.emplace_back(arr[N-1-jj]);	  
      }

      sort(negList.begin(), negList.end());
      ll kkmax = min(i, (ll)negList.size());
      for(ll kk = 0; kk < kkmax; kk++){
	tmpval -= negList[kk];
      }

#ifdef DEBUG      
      cout << "tmpval=" << tmpval << ", " << "negListSize=" << negList.size() << endl;
#endif
      
      if(tmpval > tmpmax) tmpmax = tmpval;
    }
  }

  cout << tmpmax << endl;
  
  return 0;
}


Measured memory_bytes: 256
#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;
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 main() {
  IOS;
  string s; cin >> s;
  for (int i = 1; i < 4; i++) {
    if (s[i-1] == s[i]) { COUT("Bad"); return 0; }
  }
  COUT("Good");
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <valarray>

using namespace std;

int cnt[3<<17];
int cnt2[3<<17];

main()
{
    const int mod=1e9+7;
    int n; cin>>n;
    int k; cin>>k;

    vector<vector<int>> g(n);
    for(int i=n-1; i--; )
    {
        int u,v; cin>>u>>v; --u,--v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    queue<pair<int,int>> que;
    que.emplace(0,-1);
    long long ans=k;
    while(!que.empty())
    {
        int f,p; tie(f,p)=que.front(); que.pop();
        int h=k-1;
        if(p>=0 and h) --h;
        for(int i:g[f])
        {
            if(i==p) continue;
            ans*=h;
            ans%=mod;
            h--;
            que.emplace(i,f);
        }
    }
    cout << ans << "\n";
}

Measured memory_bytes: 6904
import sys
import re

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    X, Y = input().split()
    if X < Y:
        print('<')
    elif X > Y:
        print('>')
    else:
        print('=')


if __name__ == '__main__':
    main()


Measured memory_bytes: 9792
#include <stdio.h>
#define N 8
#define FREE -1
#define NOT_FREE 1

int row[N], col[N], dpos[15], dneg[15];

void printBoard() {
	int i,j;
	for (i = 0;i < N;i++) {
		for (j = 0;j < N;j++) {
			if(row[i] == j) printf("Q");
			else printf(".");
		}
		printf("\n");
	}
}

void putQueen(int i) {
	int j;
	if(i == N) {
		printBoard();
		return;
	}

	if(row[i] != FREE) putQueen(i+1);
	else {
		for(j = 0; j < N; j++) {
			if(col[j] == NOT_FREE || dpos[i+j] == NOT_FREE || dneg[i-j+N-1] == NOT_FREE) continue;
			row[i] = j;
			col[j] = dpos[i+j] = dneg[i-j+N-1] = NOT_FREE;
			putQueen(i+1);
			col[j] = dpos[i+j] = dneg[i-j+N-1] = FREE;
			row[i] = FREE;
		}
	}
}

int main() {
	int i, j;
	int k,r,c;

	for(i = 0; i < N; i++) {
		row[i] = col[i] = FREE;
	}
	for(i = 0; i < 15; i++) {
		dpos[i] = dneg[i] = FREE;
	}

	scanf("%d", &k);
	for(i = 0; i < k; i++) {
		scanf("%d", &r);
		scanf("%d", &c);
		row[r] = col[c] = dpos[r+c] = dneg[r-c+N-1] = NOT_FREE;
		row[r] = c;
	}
	putQueen(0);

	return 0;
}



Measured memory_bytes: 2112
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPr(i, n) for(int i = (n)-1; i >= 0; --i)
#define FORq(i, m, n) for(int i = (m); i <= (n); ++i)
#define FORqr(i, m, n) for(int i = (n); i >= (m); --i)
#define MP make_pair
#define SIN(x, S) (S.count(x) != 0)
#define M0(x) memset(x, 0, sizeof(x))
#define FILL(x, y) memset(x, y, sizeof(x))
#define MM(x) memset(x, -1, sizeof(x))
#define ALL(x) (x).begin(), (x).end()
#define DB(x) cerr << #x << " = " << x << endl
#define DB2(x, y)                                                              \
    cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n";
#define DEBUG                                                                  \
    int x12345;                                                                \
    cin >> x12345;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
const long long MOD = 1e9 + 7;

///////////////////////////////////////////////
// for template
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////
/// ⸜( ⌓̈ )⸝ ///
int main() {
    int N;
    cin >> N;
    vector<ll> x(N),y(N);
    vector<ll> z,w;

    REP(i,N){
        cin >> x[i] >> y[i];
        z.push_back(x[i] + y[i]);
        w.push_back(x[i] - y[i]);
    }

    sort(ALL(z));
    sort(ALL(w));
    ll ans = max(z[N - 1] - z[0], w[N - 1] - w[0]);
    cout << ans << endl;
}

Measured memory_bytes: 9672
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    aa = LI()

    if n == 0:
        if aa[0] == 1:
            return 1
        return -1

    if aa[0] != 0:
        return -1

    b = [1]
    c = 1
    for a in aa[1:-1]:
        if a > c * 2:
            return -1
        c = c * 2 - a
        b.append(c)

    if c * 2 < aa[-1]:
        return -1

    r = c = aa[-1]
    for a,b in list(zip(aa[:-1],b))[::-1]:
        t = (c+1) // 2
        if t > b:
            return -1
        c = a + min(b, c)
        r += c

    if c != 1:
        return -1

    return r

print(main())





Measured memory_bytes: 679288
#ABC108B
x1, y1, x2, y2 = map(int, input().split())
dx = x2 - x1
dy = y2 - y1

x3 = x2 - dy
y3 = y2 + dx
 
x4 = x3 - dx
y4 = y3 - dy

print(x3, y3, x4, y4)

Measured memory_bytes: 2940
from collections import deque
import sys
input = sys.stdin.readline

n,d = map(int,input().split())
XY = [tuple(map(int, input().split())) for i in range(n)]

ans = 0

for i in range(n):
  e = XY[i][0] **2 +XY[i][1]**2
  if e <= d**2:
    ans += 1
    
print(ans)


Measured memory_bytes: 36420
#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>;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
istream& operator>>(istream&i,mint&a){i>>a.x;return i;}
ostream& operator<<(ostream&o,const mint&a){o<<a.x;return o;}

mint dp[105][10];
vector<mint> cnt(7);

void dfs(int v, int len, int i) {
    if (len == i) {
        cnt[i] += 1;
        return;
    }
    if (v == 0) {
        dfs(0,len+1,i);
        dfs(1,len+1,i);
    }
    if (v == 1) {
        dfs(0,len+1,i);
    }
    if (v == -1) {
        dfs(0,len+1,i);
        dfs(1,len+1,i);
    }
}

int main() {
    int h, w, k;
    cin >> h >> w >> k;
    for (int i = 0; i <= 6; i++) {
        dfs(-1,0,i);
    }
    dp[0][1] = 1;
    rep(i,h) {
        for (int j = 1; j <= w; j++) {
            dp[i+1][j] += dp[i][j-1] * (cnt[max(j-3,0)]*cnt[max(w-(j+1),0)]);
            dp[i+1][j] += dp[i][j] * (cnt[max(j-2,0)]*cnt[max(w-(j+1),0)]);
            dp[i+1][j] += dp[i][j+1] * (cnt[max(j-2,0)]*cnt[max(w-(j+2),0)]);
        }
    }
    cout << dp[h][k] << endl;
    return 0;
}

Measured memory_bytes: 3492
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)

int main()
{
    int n;
    cin >> n;
    if (n % 2 == 0)
    {
        cout << n / 2 << "\n";
    }
    else
    {
        cout << (n + 1) / 2 << "\n";
    }
    return 0;
}


Measured memory_bytes: 256
# 幅優先探索
from collections import deque

N = int(input())
links = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    links[a].append((b, c))
    links[b].append((a, c))

Q, K = map(int, input().split())

d = [float('inf')] * (N + 1)
d[K] = 0
q = deque([K])
while q:
    i = q.popleft()
    for j, c in links[i]:
        if d[i] + c < d[j]:
            d[j] = d[i] + c
            q.append(j)

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
#print('\n'.join(str(v) for v in result))
print(*result, sep='\n')


Measured memory_bytes: 54516
#include<iostream>
#include<cstdio>
#include <stdio.h>
#include<algorithm>
#include<cstring>
#include <string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
#include<vector>
#include<bits/stdc++.h>
#include <set>
#define ll   long long
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#define inf 0x3f3f3f3f
#define pi 3.1415926535898
using namespace std;
const int N=2e5+10;
const int mod=1e9+7;
ll f[110][110];
ll p[110][110];//(i,j)表示第I个天开J个店的收入
ll d[110];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=10;j++)
        {
            cin>>f[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=10;j++)
        {
            cin>>p[i][j];
        }
    }
    ll  maxs=-inf;
    for(int s=1;s<(1<<10);s++)
    {
        for(int i=1;i<=n;i++)
        {
            d[i]=0;
            for(int j=1;j<=10;j++)
            {
                if(f[i][j]<<(j-1)&s)
                {
                    d[i]++;
                }
            }
        }
        ll ans=0;
        for(int i = 1; i <= n; i++)
        {
            ans+=p[i][d[i]];
        }
        maxs=max(maxs,ans);
    }
    cout<<maxs<<endl;
    return 0;
}


Measured memory_bytes: 3748
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int INF=1<<30;

template <class RandomIt>
size_t msort(RandomIt first, RandomIt last) {
    if (first+1 >= last) return 0;

    using T=typename RandomIt::value_type;
    ptrdiff_t lhalf=(last-first)>>1;
    RandomIt mid=first+lhalf;

    size_t count_=0;
    count_ += msort(first, mid);
    count_ += msort(mid, last);

    ptrdiff_t rhalf=last-mid;
    vector<T> L(lhalf+1), R(rhalf+1);

    for (RandomIt in=first, out=L.begin(); in<mid; (++in, ++out))
        *out = *in;

    for (RandomIt in=mid, out=R.begin(); in<last; (++in, ++out))
        *out = *in;

    L[lhalf] = R[rhalf] = INF;

    size_t i=0, j=0;
    for (RandomIt it=first; it<last; ++it) {
        if (L[i] <= R[j]) {
            *it = L[i];
            ++i;
        } else {
            *it = R[j];
            ++j;
        }
        ++count_;
    }

    return count_;
}

int main() {
    size_t n;
    scanf("%zu", &n);

    vector<int> S(n);
    for (size_t i=0; i<n; ++i)
        scanf("%d", &S[i]);

    size_t t=msort(S.begin(), S.end());
    for (size_t i=0; i<n; ++i)
        printf("%d%c", S[i], i<n-1? ' ':'\n');

    printf("%zu\n", t);
    return 0;
}

Measured memory_bytes: 6356
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <ctime>
 
using namespace std;
 
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
 
long gcd(long a, long b){
	if (a%b==0){
		return b;
	}
	else{
		return gcd(b,a%b);
	}
}
 
long lcm(long a, long b){
	return (a*b) / gcd(a,b);
}
 
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a < b) { a = b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a > b) { a = b; return 1; } return 0; }
 
typedef long long ll;
 
const ll INF = 1ll<<60;
const ll MOD = 1000000007;
const double EPS = 1e-10;

int main(){
	int a, b, c;
	
	cin >> a >> b >> c;
	
	if (a == b) cout << c << endl;
	else if (a == c) cout << b << endl;
	else cout << a << endl;
	
	return 0;
}

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

template <class t>
using vc = vector<t>;
template <class t>
using vvc = vector<vector<t>>;
typedef long long ll;
typedef vc<int> vi;
typedef vvc<int> vvi;
typedef pair<int, int> pi;

#define endl "\n"

#define k first
#define v second
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()

#define ALL(a) a.bg, a.ed

template <class t, class u>
ostream &operator<<(ostream &os, const pair<t, u> &p) {
    return os << "( " << p.k << ", " << p.v << " )";
}

template <class t>
ostream &operator<<(ostream &os, const vc<t> &v) {
    os << "[ ";
    for (int i = 0; i < v.size(); i++) {
        os << v[i];
        if (i != v.size() - 1) {
            os << ", ";
        }
    }
    return os << " ]";
}

// g++ -std=c++17 -O2 -Wall template.cpp -o template
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << fixed << setprecision(18);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // Solution

    int a, b, c;
    cin >> a >> b >> c;
    bitset<101> m;
    int i = 1;
    long long cur = a;
    while (cur % b != c) {
        cur = a * i;
        if (m[cur % b]) {
            cout << "NO\n";
            return 0;
        }
        m[cur % b] = true;
        i++;
    }
    cout << "YES\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <iostream>
// #include <vector>
using namespace std;
using ll = long long;
constexpr ll INF = 1'010'000'000'000'000'017LL;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

int main() {
    ll n, k;
    cin >> n >> k;
    vector<double> p(n);
    double ma = 0;

    rep(i, n) cin >> p.at(i);

    rep(i, n) p.at(i) = (1 + p.at(i)) / 2;

    double sum = 0;
    rep(i, k) sum += p.at(i);

    rep(i, n - k + 1) {
        double tmp = 0;
        if(i != 0) {
            sum -= p.at(i - 1);
            sum += p.at(i + k - 1);
        }
        // cout << tmp << endl;
        ma = max(ma, sum);
    }

    cout << fixed << setprecision(15) << ma;
}

Measured memory_bytes: 1792
import sys

input = sys.stdin.readline

def main():
    ans = 0
    H, W, M = map(int, input().split())
    bombs = []
    hs = [0]*(H)
    ws = [0]*(W)
    for _ in range(M):
        h, w = map(int, input().split())
        bombs.append(tuple([h-1, w-1]))
        hs[h-1] += 1
        ws[w-1] += 1
    maxh = max(hs)
    maxw = max(ws)
    ans = maxh + maxw

    maxhindex = [i for i, x in enumerate(hs) if x == maxh]
    maxwindex = [i for i, x in enumerate(ws) if x == maxw]

    bombs = set(bombs)
    for i in maxhindex:
        for j in maxwindex:
            if (i, j) not in bombs:
                print(ans)
                exit()

    print(ans-1)

if __name__ == '__main__':
    main()

Measured memory_bytes: 90128
import java.util.Scanner;

public class Main {
	  
	public static void main(String args[]) {
		    Scanner sc = new Scanner(System.in);
		    
		    String s = sc.nextLine();
		    int count = 0;
		    for(int i = 0; i < s.length()-1; i++ ) {
		    	if(s.substring(i,i+1).equals(s.substring(i+1,i+2))) {
		    	}
		    	else {
		    		count++;
		    	}
		    }
		    System.out.println(count);
		    
		    sc.close(); }
		  }


Measured memory_bytes: 33980
#include <bits/stdc++.h>
#define RANGE(i,n) for(int i=0;i<n;i++)
typedef long long ll;
struct P{
    ll var1;
    ll var2;
};
bool operator< ( const P &one, const P &two){
    return one.var1 < two.var1;
};
bool operator> ( const P &one, const P &two){
    return one.var1 > two.var1;
};

using namespace std;

signed main() {
    string S;
    cin >> S;
    bool flag = false;
    char start = S[0];
    RANGE(i,3){
        if(start == S[i+1]) flag = true;
        start = S[i+1];
    }
    if(flag) cout << "Bad" << endl;
    else cout << "Good" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
/* AGC_1 E.BBQ Hard
   The answer is sigma(1<=i,j<=N,f(Ai+Aj,Bi+Bj)),
   while f(a,b)=C(a+b,a).
   Unfortunately,O(n^2) solution will get a TLE.
   So consider the geometric meaning for the answer.
   f(a,b) is equal to the way to go from (0,0) to (a,b).
   So f(Ai+Aj,Bi+Bj) equals to the way to go from (-Ai,-Bi) to (Aj,Bj).
   Do simple DP to solve it.
   And what's more,
   if the total answer is X,
   ans=(X-sigma(1<=i<=N,f(Ai*2,Bi*2)))/2,
   and f(Ai*2,Bi*2) can be got by pre-calculating the C(a,b).
*/
int a[200005],b[200005],n;
int f[8005][8005];
int main (){
	int i,j;
	scanf ("%d",&n);
	for (i=1;i<=n;i++)
	{scanf ("%d%d",&a[i],&b[i]);
	f[2005-a[i]][2005-b[i]]++;
	}
	for (i=1;i<=4005;i++)
	{for (j=1;j<=4005;j++)
	{f[i][j]=f[i][j]+f[i-1][j]+f[i][j-1];
	while (f[i][j]>=mod) {f[i][j]-=mod;}
	}
	}
	int ans=0;
	for (i=1;i<=n;i++)
	{ans+=f[2005+a[i]][2005+b[i]];
	while (ans>=mod) {ans-=mod;}
	}
	memset (f,0,sizeof(f));
	f[0][0]=1;
	for (i=1;i<=8000;i++)
	{f[i][0]=1;f[i][i]=1;
	for (j=1;j<i;j++)
	{f[i][j]=f[i-1][j]+f[i-1][j-1];
	while (f[i][j]>=mod) {f[i][j]-=mod;}
	}
	}
	for (i=1;i<=n;i++)
	{ans-=f[2*(a[i]+b[i])][a[i]*2];
	while (ans<0) {ans+=mod;}
	}
	if (ans%2==1) {ans+=mod;}
	printf ("%d",ans/2);
	return 0;
}
	

Measured memory_bytes: 252160
def func():
    N = int(input())
    if(N < 105):
        print(0)
        return

    prime = []
    isPrime = [True for i in range(201)]
    isPrime[0] = isPrime[1] = False
    for i in range(2, 201):
        if(isPrime[i]):
            prime.append(i)
            for j in range(2 * i, 201, i):
                isPrime[j] = False

    ans = 0
    for a in range(105, N + 1, 2):
        cnt = []
        num = a
        for i in range(len(prime)):
            divCnt = 0
            while(num % prime[i] == 0):
                num //= prime[i]
                divCnt += 1
            if(divCnt > 0):
                cnt.append(divCnt)
        divisorCnt = 1
        for i in range(len(cnt)):
            divisorCnt *= cnt[i] + 1
        if(divisorCnt == 8):
            ans += 1
    print(ans)

if __name__ == '__main__':
    func()

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
vector<vector<int> > nyu(int h, int w) {
	vector<vector<int> > a(h + 2, vector<int>(w + 2, h*w + 1));
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> a[i + 1][j + 1];
		}
	}
	return a;
}
vector<int> nyu1(int n) {
	vector<int> c(n);
	for (int i = 0; i < n; i++) {
		cin >> c[i];
	}
	return c;
}
long long rui(int n) {
	if (n == 0) {
		return 1;
	}
	else {
		return 2 * rui(n - 1);
	}
}
long long pad(int n, long long x) {
	if (n == 0) {
		return 1;
	}
	else if (x == 1) {
		return 0;
	}
	else {
		long long a = rui(n+1) - 3;
		if (x <= a + 1) {
			return pad(n - 1, x - 1);
		}
		else if (x == a + 2) {
			return rui(n);
		}
		else if (x == 2*a + 3) {
			return 2 * rui(n) - 1;
		}
		else {
			return rui(n) + pad(n-1, x - a - 2);
		}
	}
}
int main() {
	int n; long long x;
	cin >> n >> x;
	cout << pad(n, x) << endl;
}

Measured memory_bytes: 256
import itertools
import math

N = int(input())
x =[]
y = []
for i in range(N):
    a, b = map(int,input().split())
    x.append(a)
    y.append(b)

dist = 0

for i in range(N):
    for j in range(N):
        dist += ((x[i]-x[j])**2+(y[i]-y[j])**2)**0.5 

dist = dist/N

print(dist)

Measured memory_bytes: 3064
#include<stdio.h>
#include<math.h>
int main()
{
	long long a,b,c;
	scanf("%lld%lld%lld",&a,&b,&c);
	if(c-a-b<0)
	printf("No");
	else
	{
		if((c-a-b)*(c-a-b)-4*a*b>0)
		printf("Yes");
		else
		printf("No");
	}
	return 0;
}

Measured memory_bytes: 128
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N=Integer.parseInt(sc.next());
        int[] tokuten = new int[N];
        int[][] kaisu=new int[101][3];
        Arrays.fill(tokuten, 0);
        int[][] kaita= new int[N][3];
        for(int i=0;i<N;i++){
            for(int j=0;j<3;j++){
                kaita[i][j]=Integer.parseInt(sc.next());
                kaisu[kaita[i][j]][j]++;
            }
        }
        for(int i=0;i<N;i++){
            for(int j=0;j<3;j++){
                if(kaisu[kaita[i][j]][j]==1){
                    tokuten[i]+=kaita[i][j];
                }
            }
        }
        for(int i=0;i<N;i++){
            System.out.println(tokuten[i]);
        }
    }
}

Measured memory_bytes: 20272
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005,M=1e9+7;
ll fac[N]= {1,1},inv[N]= {1,1},f[N]= {1,1},pos[N];
ll C(ll a,ll b) {
    if(b>a)
        return 0;
    return fac[a]*inv[b]%M*inv[a-b]%M;
}
void init() { //快速计算阶乘的逆元
    for(int i=2; i<N; i++) {
        fac[i]=fac[i-1]*i%M;
        f[i]=(M-M/i)*f[M%i]%M;
        inv[i]=inv[i-1]*f[i]%M;
    }
}
int main() {
    init();
    int n;
    scanf("%d",&n);
    n++;
    long long m,x;
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &x);
        if (pos[x]) {
            m = n - (i - pos[x] + 1);
            break;
        }
        pos[x] = i;
    }
    for(int i=1; i<=n; i++) {
        printf("%lld\n", (C(n, i) - C(m, i-1)+M) % M);

    }
}


Measured memory_bytes: 4352
//
//  main.cpp
//  Rainy Season
//
//  Created by Bryan on 15/08/20.
//  Copyright © 2020 mac. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;

int main()
{
    string s;
    cin>>s;
    int maks = 0;
    int cur = 0;
    for (int f = 0; f<3;f++)
    {
        if (s[f] == 'R')
            cur++;
        else
        {
            if (maks<cur)
                maks = cur;
            cur = 0;
        }
    }
    if (maks<cur)
        maks = cur;
    printf ("%d\n",maks);
}


Measured memory_bytes: 3676
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define bg begin()
#define ed end()
#define rbg rbegin()
#define red rend()
#define all(x) x.bg,x.ed
#define rall(x) x.rbg,x.red
#define pb push_back
#define pf push_front
#define eb emplace_back
using namespace std;
typedef long long ll;
template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b; return true;} return false;}
template<class t,class u> bool chmin(t&a,u b){if(a>b){a=b; return true;} return false;}
template<class t,class u> t MAX(t a,u b){if(a>=b) return a; return b;}
template<class t,class u> t MIN(t a,u b){if(a<=b) return a; return b;}
template<class t> int SIZE(t s){return (int)s.size();}
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using vvi=vc<vc<int>>;
using pi=pair<int,int>;
using vi=vc<int>;
void yes(){ cout << "Yes" << endl; }
void no(){ cout << "No" << endl; }
const long long INF = 1LL << 60;

int main(){
    cout << fixed << setprecision(20);
    string s,t; cin >> s >> t;
    int si = SIZE(s);
    int ans = 0;
    rep(i,si){
        if(s[i] == t[i])ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
const int N= 1e7+5;
int n,t,k,m;

string s1,s2;

int32_t main()
{
	IOS;
	cin>>s1;
	cin>>s2;
	int n= s1.length();
	if(s2.substr(0,n)== s1)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	
}
	 


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define md 1000000007
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n, i = 0, j= 0, k = 0, l = 0, m = 0, a = 0, b = 0, sum = 0, x = 0, y = 0, z = 0, c, p;
    cin >> n;
    long long arr[n+1][3], dp[n+1][3];
    for(i = 1; i <= n; i++){
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
    }
    dp[1][0] = arr[1][0]; dp[1][1] = arr[1][1]; dp[1][2] = arr[1][2];
    for(i = 2; i <= n; i++){
        dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + arr[i][0];
        dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + arr[i][1];
        dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + arr[i][2];
        //cout << " " << dp[i][0] << " "  << dp[i][1] << " " << dp[i][2] << endl;
    }
    m = dp[n][0];
    l = max(dp[n][1],dp[n][2]);
    cout << max(l,m);

    return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;


int main(){
  
    ll n; cin>>n;
    vector<ll> op;
    while(abs(n)){
        ll s = (n%2+2)%2;
        op.push_back(s);
        n = -(n-s)/2;
    }
    for(ll i=0; i<op.size(); i++){
        cout<<op[op.size()-i-1];
    }
    if(op.size()==0)cout<<0;
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
s=list(input())

s.reverse()

f=1
n=len(s)

a1=list("dream")
a2=list("dreamer")
a3=list("erase")
a4=list("eraser")

a1.reverse()
a2.reverse()
a3.reverse()
a4.reverse()

while f>0 and n>0:
    k=-1
    if n>=7:
        if s[0:7]==a2:
            k=7
    if n>=6:
        if s[0:6]==a4:
            k=6
    if n>=5:
        if s[0:5]==a1:
            k=5
        elif s[0:5]==a3:
            k=5
    
    if k>0:
        del s[0:k]
        n=len(s)
    else:
        f=-1

if f>0:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3956
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define dup(x,y) (((x)+(y)-1)/(y))
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const double EPS = 1e-10;
const int INF = 1e9;
const ll LINF = 1e15;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int main() {
	int k;
	cin >> k;
	string s;
	cin >> s;
	int n = s.size();
	rep(i,n) {
		if (i == k) {
			cout << "...";
			break;
		}
		else cout << s[i];
	}
	cout << endl;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using Vbo = vector<bool>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVbo = vector<Vbo>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
#define rep2(i, m, n) for(ll i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(ll i=int(m)-1; i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << " "; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline int Log2(ll x) { int k; for (k = 0; x > 0; ++k) x >>= 1; return k; } // number of binary digits
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;


ll n, m, q;
V a, b, c, d;
int rec(V x) {
  int k = x.size();
  int res = 0;
  if (k == n) {
    rep(i, q) if (x[b[i]] - x[a[i]] == c[i]) res += d[i];
    return res;
  }
  else {
    x.push_back(0);
    rep2(i, x[k-1], m+1) {
      x[k] = i;
      chmax(res, rec(x));
    }
  }
  return res;
}

int main() {
  cin >> n >> m >> q;
  a.assign(q, 0);
  b.assign(q, 0);
  c.assign(q, 0);
  d.assign(q, 0);
  rep(i, q) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    --a[i];
    --b[i];
  }

  int ans = rec(V(1, 1));
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 3652
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
P = LIST()

acc = [0]*N
for i in range(N):
	su = (P[i]*(P[i]+1)/2)/P[i]
	acc[i] = su

accs = [0]*N
accs[0] = acc[0]
for i in range(1, N):
	accs[i] = accs[i - 1] + acc[i]

ma = 0
for i in range(K - 1, N):
	ma2 = 0
	if i == K - 1:
		ma2 = accs[i]
	else:
		ma2 = accs[i] - accs[i - K]
	if ma < ma2:
		ma = ma2

print(ma)

Measured memory_bytes: 27128
/*The woods are lovely, dark and deep,
But I have promises to keep,
And miles to go before I sleep,
And miles to go before I sleep.*/

//PRABHJOT SINGH A.K.A. PRABHI
//~~~~~conquizztador~~~~~


#include<bits/stdc++.h>
using namespace std;
using lli = long long int;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
const int MOD = 1000000007;
const int MOD1 = 998244353;
const int maxn = 100010;
const int lim = (int)1e9;
vector<int> v[2 * maxn];
vector<lli> counter;
void dfs(int node, int pre)
{
	if (pre != -1)
		counter[node] += counter[pre];
	for (auto i : v[node])
		if (i != pre)
			dfs(i, node);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n = 0, q = 0, x = 0, y = 0, p = 0;
	cin >> n >> q;
	for (int i = 0; i + 1 < n; ++i)
	{
		cin >> x >> y; --x; --y;
		v[x].pb(y);
		v[y].pb(x);
	}
	counter.resize(n);
	counter.assign(n, 0);
	while (q--)
	{
		cin >> p >> x;
		--p;
		counter[p] += x;
	}
	dfs(0, -1);
	for (auto i : counter)
		cout << i << " ";
}

Measured memory_bytes: 25068
#include<iostream>
#include<cstdio>
using namespace std;
char s[10];
bool read()
{
	scanf("%s",s);
	return s[0]=='Y';
}
int main()
{
	long long n=1;
	for(int i=0;i<=10;i++,n=n*10)
	{
		printf("? %lld\n",n);fflush(stdout);
		if(!read()) break;
	}
	if(n==100000000000LL)
	{
		n=1;
		for(int ck=2;ck<=2000000000;ck=ck*10,n=n*10)
		{
			printf("? %d\n",ck);fflush(stdout);
			if(read())
			{
				printf("! %lld\n",n);fflush(stdout);
				return 0;
			}
		}
	}
	//cout<<n<<endl;
	long long ma=n/10;
	for(n=0;ma>1;ma/=10,n=n*10)
	{
		int l=-1,r=8,mid;
		while(l<r)
		{
			mid=(l+r+1)/2;
			printf("? %lld\n",n+mid+1);fflush(stdout);
			if(!read()) r=mid-1;
			else l=mid;
		}
		n+=l+1;
	}
	n*=10;
	for(int i=8;i>=0;i--)
	{
		printf("? %lld\n",n+i*10);fflush(stdout);
		if(!read())
		{
			printf("! %lld\n",n/10+i+1);fflush(stdout);
			return 0;
		}
	}
	printf("! %lld\n",n/10);fflush(stdout);
	return 0;
}
		

Measured memory_bytes: 684
#include <bits/stdc++.h>
 
using namespace std;
using namespace std::chrono;
 
#define rep(i,a,b) for(int i = a;i<(b);++i)
#define trav(a,v) for(auto& a : v)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
 
ll big = 1000000007ll;
ll big2 = 1000000009ll;
ll n,m,T,k,q;
 
vector<vector<ll> > C(100001, vector<ll>());
vector<vector<ll> > CW(100001, vector<ll>());
 
ll ans = 0;
ll miw = big;
 
ll middle = -1;
 
ll totsum = 0;
 
ll SS[100001] = {0};
 
ll dfs(ll i, ll par, ll w){
    ll ss = 1;
    for(ll c1 = 0; c1 < sz(C[i]); c1++){
        ll a = C[i][c1];
        if(a != par){
            ll w2 = CW[i][c1];
            miw = min(miw,w2);
            ss += dfs(a,i,w2);
        }
    }
 
    if(par != -1){
        if(ss == n-ss){
            middle = w;
        }
        ans += (2*min(ss,n-ss)) * w;
    }
    SS[i] = ss;
 
    return ss;
}
 
ll centroid(ll i, ll par){
    ll ma = 0;
    ll j = 0;
    for(ll c1 = 0; c1 < sz(C[i]); c1++){
        ll a = C[i][c1];
        if(a != par){
            if(ma < SS[a]){
                j = a;
                ma = SS[a];
            }
        }
    }
    if(ma <= n/2)return i;
    return centroid(j,i);
}
 
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("autput.txt","w",stdout);
    ll a,b,c,d,e,f;
 
    cin >> n;
    for(ll c1 = 0; c1 < n-1; c1++){
        cin >> a >> b >> c;
        a--;
        b--;
        C[a].push_back(b);
        C[b].push_back(a);
        CW[a].push_back(c);
        CW[b].push_back(c);
        totsum += c;
    }
    dfs(0,-1,-1);
    if(middle != -1){
        cout << ans-middle << "\n";
    }
    else{
 
        c = centroid(0,-1);
        ll miw = big;
        for(ll c1 = 0; c1 < sz(C[c]); c1++){
            miw = min(miw,CW[c][c1]);
        }
        cout << ans-miw << "\n";
    }
 
 
    return 0;
}

Measured memory_bytes: 17408
def main():
    n, k = [int(i) for i in input().split()]
    h = [int(i) for i in input().split()]
    dp = [float('inf')] * n
    dp[0] = 0

    for i in range(1, n):
        for j in range(max(i - k, 0), i):
            np = dp[j] + abs(h[i] - h[j])
            if np < dp[i]:
                dp[i] = np 
    
    print(dp[n - 1])

main()


Measured memory_bytes: 54368
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,W;
  cin >> n >> W;
  vector<int> w(n),v(n);
  for(int i=0;i<n;i++){
    cin >> w[i] >> v[i];
  }
  vector<vector<long long>> d(n+1,vector<long long>(W+1));
  for(int i=0;i<n;i++){
    for(int j=0;j<=W;j++){
      if(j>=w[i]){
        d[i+1][j]=max(d[i][j-w[i]]+v[i],d[i][j]);
      }
      else{
        d[i+1][j]=d[i][j];
      }
    }
  }
  cout << d[n][W] << endl;
}

Measured memory_bytes: 80256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>
#include <climits>
#include <iterator>
#include <iomanip>
#include <stack>
#include <set>
#include <cstdio>
#include <bitset>
#include <functional>
#include <tuple>
#include <list>
#include <deque>
using namespace std;
typedef pair<int, int> P;

#define FOR(i, a, n) for (ll i = (ll)a; i<(ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

typedef long long ll;
typedef vector<int> VI;

int main() {
    cin.tie(0);
   	ios::sync_with_stdio(false);
    
    int n; cin >> n;
    int bit=0;
    int k; cin >> k;
    for(int i=0; i<k; ++i){
        int b; cin >> b;
        bit|=(1<<b);
    }
    vector<int> elem;
    for(int sub = bit; ; sub = (sub-1)&bit) {
        elem.push_back(sub);
        if(!sub) break;
    }
    
    sort(elem.begin(), elem.end());
    
    REP(i, elem.size()){
        cout << elem[i] << ":";
        REP(j, n) if((elem[i]>>j)&1) cout << " " << j;
        cout << endl;
    }
	return 0;
}


Measured memory_bytes: 3948
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
using namespace std;

int main() {
  ll a, b, x;
  cin >> a >> b >> x;
  if(a != 0)cout << (b/x+1) - ((a-1)/x+1);
  else cout << b /x+1;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;
typedef long long ll;
const int MAXN = 105;
int n,m;
char str[MAXN][MAXN];
int f[MAXN][MAXN];

int main()
{
    cin >> n >> m;
    for(int i = 1; i<=n; i++)
        cin >> str[i]+1;
    f[1][1] = str[1][1]=='#';
    for(int i = 2; i<=n; i++)
	    f[i][1] = f[i-1][1]+(str[i][1]=='#'&&str[i-1][1]=='.');
	for(int i = 2; i<=m; i++)
	    f[1][i] = f[1][i-1]+(str[1][i]=='#'&&str[1][i-1]=='.');
	for(int i = 2; i<=n; i++)
	    for(int j = 2; j<=m; j++)
		    f[i][j] = min(f[i-1][j]+(str[i][j]=='#'&&str[i-1][j]=='.'),
			   			  f[i][j-1]+(str[i][j]=='#'&&str[i][j-1]=='.'));
	cout << f[n][m] << endl; 
	return 0;
}
     

Measured memory_bytes: 256
#line 2 "../../library/template.hpp"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0; i < (ll)n; i++)
#define rep3(i, l, r) for(ll i = l; i < (ll)r; i++)
#define per(i, n) for(ll i = (ll)n-1; i >= 0; i--)
#define per3(i, l, r) for(ll i = (ll)r-1; i >= (ll)l; i--)
#define all(v) begin(v), end(v)
template<class T, class U>
inline void cmax(T& a, U b) { if (a < b) a = b; }
template<class T, class U>
inline void cmin(T& a, U b) { if (a > b) a = b; }

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(15);
  }
} io_setup;

constexpr char el = '\n';

template<class T, class U>
ostream &operator<<(ostream &os, const pair<T, U>& p) {
  os << p.first << " " << p.second;
  return os;
}
template<class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
  is >> p.first >> p.second;
  return is;
}
template<class T>
ostream &operator<<(ostream &os, const vector< T > &v) {
  rep(i, v.size())
    os << v[i] << (i + 1 != v.size() ? " " : "");
  return os;
}
template<class T>
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}
#line 2 "a.cpp"

int main() {
  ll n;
  cin >> n;
  ll ans = 0;
  while (n > 0) {
    if (n >= 10 and n%10 != 9) {
      n -= n%10+1;
    }
    ans += n%10;
    n /= 10;
  }
  cout << ans << endl;
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    vector<string> weathers = {"Sunny", "Cloudy", "Rainy"};
    auto get_index = [&](string t) {
        for (int i = 0; i < (int) weathers.size(); ++i) {
            if (weathers[i] == t) {
                return i;
            }
        }
        return -1;
    };
    cout << weathers[(get_index(s) + 1) % 3] << endl;
    return 0;
}


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

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int x = sc.nextInt();
    boolean can =false;
    for(int i = 1; i <= b; i++){
        if( (i * a) % b == x) {
          can =true;
        }
    }
    if(can){
      System.out.println("YES");
    }else{
      System.out.println("NO");
    }

  }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int a,b;
  cin >> a >> b;
  for(int i = 12; i <= 1250; i++){
    if(int(i * 2 / 25) == a && int(i / 10) == b){
      cout << i << endl;
      return 0;
    }
  }
  cout << "-1" << endl;
}

Measured memory_bytes: 256