akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <boost/multiprecision/cpp_int.hpp>
#define rep0(i, n) for(int i=0; i<(int)(n);i++)
typedef int64_t lint;
using namespace std;

int main(){
    lint n, k;
    cin >> n >> k;
    vector<lint> a(n);
    rep0(i, n){
        cin >> a[i];
    }
    lint kk = k * (k - 1) / 2;
    boost::multiprecision::cpp_int ans = 0;
    for (int i = 0; i < n; ++i) {
        lint left = 0;
        lint right = 0;
        for (int j = 0; j < n; ++j) {
            if(a[i] > a[j]){
                if(i > j)left ++ ;
                if(i < j)right ++ ;
            }
        }
        rep0(j,left)
        {
            ans += kk;
            //ans %= 1000000007;
        }
        rep0(j,right)
        {
            ans += kk;
            ans += k;
            //ans %= 1000000007;
        }
        ans %= 1000000007;

    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int A, B, C;
	cin >> A >> B >> C;
	int D = A + B;

	if (D > C || D == C) {
		cout << "Yes" << endl;
	}

	else if (D < C) {
		cout << "No" << endl;
	}
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define si(x) int(x.size())
const int mod=1000000007,MAX=200005,INF=1<<29;

vector<int> G[MAX];
int dis[MAX][2],dis2[MAX];
vector<int> diameter;
int N;

void pre(int u,int p,int k){
    for(int to:G[u]){
        if(to==p) continue;
        dis[to][k]=dis[u][k]+1;
        pre(to,u,k);
    }
}

void make(int u,int p,int goal,bool &flag){
    if(u==goal){
        diameter.push_back(u);
        flag=true;
        return;
    }
    for(int to:G[u]){
        if(to==p) continue;
        make(to,u,goal,flag);
        if(flag){
            diameter.push_back(u);
            return;
        }
    }
}

bool check=true;

void BFS(){
    queue<int> Q;
    for(int i=0;i<N;i++) dis[i][0]=INF;
    for(int a:diameter){
        dis[a][0]=0;
        Q.push(a);
    }
    
    while(!Q.empty()){
        int u=Q.front();Q.pop();
        for(int to:G[u]){
            if(dis[to][0]==INF){
                dis[to][0]=dis[u][0]+1;
                if(dis[u][0]) check=false;
                Q.push(to);
            }
        }
    }
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>N;
    for(int i=0;i<N-1;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    for(int i=0;i<N;i++){
        dis[i][0]=dis[i][1]=INF;
    }
    dis[0][0]=0;
    pre(0,-1,0);
    pair<int,int> ma={0,0},ma2={0,0};
    for(int i=0;i<N;i++) chmax(ma,{dis[i][0],i});
    dis[ma.second][1]=0;
    pre(ma.second,-1,1);
    for(int i=0;i<N;i++) chmax(ma2,{dis[i][1],i});
    bool flag=false;
    make(ma.se,-1,ma2.se,flag);
    
    BFS();
    
    if(!check){
        cout<<-1<<endl;
        return 0;
    }
    
    vector<int> ans(N,INF);
    
    for(int q=0;q<2;q++){
        vector<int> res;
        int now=1;
        
        for(int a:diameter){
            int cnt=0;
            for(int to:G[a]){
                if(dis[to][0]==0) continue;
                cnt++;
            }
            for(int i=1;i<=cnt;i++) res.push_back(now+i);
            res.push_back(now);
            now+=cnt+1;
        }
        
        chmin(ans,res);
        reverse(all(diameter));
    }
    
    for(int a:ans) cout<<a<<" ";
    cout<<endl;
    
}


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

using namespace std;

#define llong long long int
#define rep(i, n) for (int i = 0; i < n; ++i) 
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define stl_repr(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()

const static llong MOD = 1000000000 + 7;
const static int inf = INT_MAX / 2;
const static llong INF = 1LL << 31;
const static int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int main (int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, x;
    cin >> n >> x;
    vector<int> L(n);
    rep(i, n) cin >> L[i];
    int ans = 1;
    int d = 0;
    rep(i, n) {
        d = d + L[i];
        if (d <= x) ++ans;
    }

    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
//written by libra9z
#include <bits/stdc++.h>
using namespace std;
long long n,z,w,a[2005],ans,b[2005];
int main()
{
	cin>>n>>z>>w;
	for (int i=0;i<n;++i)
	{
		cin>>a[i];
	}
    if (n==1)
	{
        ans=abs(a[0]-w);
        cout<<ans<<endl;
        return 0;
    }
    for (int i=0;i<n;++i) b[i]=abs(a[i]-a[n-1]);
    ans=max(abs(a[n-1]-w),b[n-2]);
    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
use proconio::{input, fastout};
use std::cmp::max;


#[fastout]
fn main() {
    input! {
        n: usize,
        aaa: [isize; n],
    }

    if n % 2 == 0 {
        let mut fwd = vec![0];
        let mut bwd = vec![0];
        let acc_func = |t: &mut isize, &a| {
            *t += a;
            Some(*t)
        };
        fwd.extend(aaa.iter().step_by(2).scan(0, acc_func));
        bwd.extend(aaa.iter().rev().step_by(2).scan(0, acc_func));
        let ans = fwd.iter().zip(bwd.iter().rev()).map(|(f, b)| f + b).max().unwrap();
        println!("{:?}", ans);
    } else {
        const NINF: isize = -1_000_000_000_000_000_000;
        //                                  [直前は取ってない]  [直前に取った]
        // 連続して取らないことができる残り回数  0, 1, 2           0, 1, 2
        let mut dp = (NINF, NINF, 0isize, NINF, NINF, NINF);
        for a in aaa {
            dp = (
                max(dp.3, dp.1),
                max(dp.4, dp.2),
                dp.5,
                dp.0 + a,
                dp.1 + a,
                dp.2 + a,
            );
        }
        println!("{:?}", max(dp.1, dp.3));
    }
}

Measured memory_bytes: 7416
l, r = map(int, input().split())

output = 2019
if r - l < 2018:
    for i in range(l, r+1):
        for j in range(l, r+1):
            if i < j:
                value = ((i%2019) * (j%2019)) % 2019
                if value < output:
                    output = value
else:
    output = 0

print (output)

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

int main() {
    int n;
    cin >> n;
    int arr[n];
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    bool state = true;
    for(int i = 0; i < n; i++) {
        if(arr[i] % 2 == 0) {
            if(arr[i] % 3 != 0 && arr[i] % 5 != 0) {
                cout << "DENIED" << endl;
                state = false;
                break;
            }
        }
    }
    if(state == true) {
        cout << "APPROVED" << endl;
    }
}

Measured memory_bytes: 256
function Main(input){
	input = input.split("\n");
  var N = ~~input[0];
  var a = input[1].split(" ").map(b=>~~b);
  var sum = 0;
  for(var i = 0; i < N ; i++){
  	sum += a[i];
  }
  var avr = sum/N;
  for(var i = 0; i < N ; i++){
    a[i] = (a[i] - avr) * (a[i] - avr);
  }
  var smallestIndex = 0;
  var smallestValue = a[0];
  for(var i = 1; i < N ; i++){
   	if(smallestValue > a[i]){
    	smallestIndex = i;
      smallestValue = a[i];
    }
  }
  return smallestIndex;
}

// If you are interested in the algorithms I used, 
// there is no need to read down from this line.

((b,c,d)=>"undefined"!=typeof require?console.log(Main(require("fs").readFileSync("/dev/stdin","utf8"))):[b=b.split("\n").slice(1,-1).join("\n"),c=function(){try{return Main(b)}catch(f){return f.stack||f.message}}(),d=typeof c,"string"==d||(c=JSON.stringify(c)),$("<form>").append([[10,b],0,[1,d],0,[10,c]].map(f=>$(f?"<textarea>":"<br>",f&&{rows:f[0],cols:40,text:f[1]}))).appendTo("body")])(`
3
1 2 3
`);

Measured memory_bytes: 21064
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>

using namespace std;

int main(){
  int a, b;
  cin >> a >> b;
  if(a < b) for(int i = 0; i < b; i++) cout << a;
  else for(int i = 0; i < a; i++) cout << b;
  cout << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int a,b,c,d,n,count,l;
    while(scanf("%d",&n)==1){
            count=0;l=0;
        for(a=0; a<10;a++){
            for(b=0; b<10; b++){
                for(c=0; c<10; c++){
                    for(d=0; d<10; d++){
                        if(a+b+c+d==n)count++;
   /* printf("%d%d%d%d\n",a,b,c,d);l++;*/
                    }
                }
            }
        }
        printf("%d\n",count);
        /*printf("The loop count=%d\n",l);*/
    }
    return 0;
}



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

int gcd(int a, int b){
    int c,d;
    c=max(a,b); d=min(a,b);
    while(d>0){
        int tmp=c;
        c=d;
        d=tmp%d;
    }
    return c;
}

int main(void){
    int N; cin >> N;
    int ans;
    cin >> ans;
    for(int i=0; i<N-1; i++){
        int a; cin >> a;
        ans=gcd(ans,a);
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

q = deque()
d = [[-1]*w for x in range(h)]

for i in range(h):
    for j in range(w):
        if m[i][j] == "#":
            q.append([i,j])
            d[i][j] = 0

aa = 0
while q:
    v = q.popleft()
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "#"
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1
            aa = max(aa,d[ny][nx])

######
print(aa)

Measured memory_bytes: 176604
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <thread>
#include <atomic>
#include <mutex>
#include <future>
#define int long long
#define endre getchar();getchar();return 0
#define INF 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define input() for(int i=0;i<n;i++)cin>>a[i];
#define P pair<int,int>
#define prique priority_queue<int,vector<int>,greater<int>>
using namespace std;
bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return (y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int n) {
	if (n == 0)return 1;
	return (kai(n - 1)*n) % INF;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x%mod;
		}
		x = x * x%mod;
		y >>= 1;
	}
	return res;
}
int mystoi(string s) {
	int cnt = 0;
	for (int i = 0; i < s.size(); i++) {
		cnt += (int)(s[i] - '0') * pow(10, s.size() - i - 1);
	}
	return cnt;
}
int h, w, n, a[10005], c[105][105];
signed main() {
	cin >> h >> w >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];
	int memo = 1, cnt = 0;
	for (int i = 0; i < h; i++) {
		if (i % 2 == 0) {
			for (int j = 0; j < w; j++) {
				c[i][j] = memo;
				cnt++;
				if (cnt == a[memo]) {
					cnt = 0;
					memo++;
				}
			}
		}
		else {
			for (int j = w - 1; j >= 0; j--) {
				c[i][j] = memo;
				cnt++;
				if (cnt == a[memo]) {
					cnt = 0;
					memo++;
				}
			}
		}
	}
	rep(i, h) {
		rep(j, w)cout << c[i][j] << " ";
		cout << endl;
	}
	endre;
}

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

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif

    string s;
    cin >> s;
    i64 ans = 0;
    int n = s.size();
    int bs = 0;
    int i = n - 1;
    while (i >= 0) {
        if (s[i] == 'A') ans += bs, --i;
        else if (s[i] == 'C') {
            if (i && s[i - 1] == 'B') i -= 2, ++bs;
            else bs = 0, --i;
        } else bs = 0, --i;
    }
    cout << ans << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


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

using namespace std;
using ll=long long;

#define faster ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define cint int t;cin>>t;while(t--)
#define rep(i,a,b) for(int i=a;i<b;i++)

int mod=1e9+7;


int check(int n,int m,int h,int w){
    if(n>=0&&n<h&&m>=0&&m<w) return 1;

    return 0;
}

int main(){
    faster;

    int h,w;
    cin>>h>>w;

    char a[h][w];

    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>a[i][j];
        }
    }

    ll maxq=0;

    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(a[i][j]=='#') continue;
            queue<pair<ll,pair<int,int>>> q;
            q.push({0,{i,j}});

            vector<vector<int>> vp(h,vector<int>(w,0));
            vp[i][j]=1;

            while(!q.empty()){
                auto k=q.front();

                ll f=k.first;
                int g=k.second.first;
                int d=k.second.second;
                q.pop();
                vp[g][d]=1;
//                if(f==1) cout<<g<<" "<<d<<endl;
                maxq=max(f,maxq);

                if(check(g+1,d,h,w)==1&&vp[g+1][d]==0&&a[g+1][d]=='.') {
                    q.push({f+1,{g+1,d}});
                    vp[g+1][d]=1;
                }if(check(g,d+1,h,w)==1&&vp[g][d+1]==0&&a[g][d+1]=='.') {
                    q.push({f+1,{g,d+1}});
                    vp[g][d+1]=1;
                }if(check(g-1,d,h,w)==1&&vp[g-1][d]==0&&a[g-1][d]=='.') {
                    q.push({f+1,{g-1,d}});
                    vp[g-1][d]=1;
                }if(check(g,d-1,h,w)==1&&vp[g][d-1]==0&&a[g][d-1]=='.') {
                    q.push({f+1,{g,d-1}});
                    vp[g][d-1]=1;
                }
            }
        }
    }

    cout<<maxq<<endl;
}


Measured memory_bytes: 256
char s[102];A(){char a[101],b[101],t,t2;return sscanf(s,">'%[=]#%[=]%c%c",a,b,&t,&t2)==3&&t=='~'&&strlen(a)==strlen(b);}B(){short*q;char*p=s,l=0;if(*(q=p++)=='^>'){for(;*(q=++p)=='=Q';p++)l++;if(l>0&&*(q=p++)=='~~'&&*++p==0)return 1;}return 0;}main(){scanf("%*d\n");for(;~scanf("%[^\n]\n",s);){puts(A()?"A":B()?"B":"NA");}}

Measured memory_bytes: 0
n = int(input())
cardslist = []

for i in range(n):
    input_cards = input().split()
    cardslist.append(input_cards)

for mark in "SHCD":
    for i in range(1, 14):
        if [mark, str(i)] not in cardslist:
            print(mark + " " + str(i))



Measured memory_bytes: 5592
mo=10^9+7
main=do
 [a,b,c,d]<-map read.words<$>getLine
 print$flip mod mo$(f a b)-(f(c+1)b)-(f a(d+1))+f(c+1)(d+1)
f x y=mod(g[x+1..x+y]*p(g[1..y])(mo-2))mo
p a b
 |b==0=1
 |odd b=mod(a*p a(b-1))mo
 |even b=p(mod(a*a)mo)$div b 2
g=foldr1$(flip mod mo.).(*)

Measured memory_bytes: 71036
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
using namespace std;
#define int long long


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

    int a,b,c; cin >> a >> b >> c;

    cout << c << " " << a << " " << b << endl;;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main ()
{
    string s;
    cin>>s;
    int shuma=0;
    for(int i=0;i<3;i++)
    {
      for(int j=i+1;j<4;j++)
      {
          if(s[i]==s[j])
          {
              shuma++;
          }
      }
    }
    if(shuma==2)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
///Bismillahir Rahmanir Rahim
#include "bits/stdc++.h"

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll inf=1e18;
const int mod=1e9+7;
const int M=100005;

 main()

{
    fast
    int cnt=0,n,x;
    cin>>n;
    f(i,1,n)
    {
        cin>>x;
        if(x%2==1 && i%2==1)cnt++;
    }
    cout<<cnt<<endl;
    return 0;

}





































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

int main()
{
    string S;
    cin >> S;
    int cur = S.size()-1;
    while(cur > 0) {
        if(cur - 4 >= 0) {
            string Ssub = S.substr(cur-4, 5);
            if(Ssub == "dream" || Ssub == "erase") {
                cur -= 5; 
                continue;
            }
        }
        if(cur - 5 >= 0) {
            string Ssub = S.substr(cur-5, 6);
            if(Ssub == "eraser") {
                cur -= 6;
                continue;
            }
        }
        if(cur - 6 >= 0) {
            string Ssub = S.substr(cur-6, 7);
            if(Ssub == "dreamer"){
                cur -= 7;
                continue;
            }
        }
        break;
    }

    if(cur > 0) cout << "NO" << endl;
    else cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<complex>
using namespace std;
typedef complex<double> p;

int main()
{
	p a,b,c,d;
	while(cin>>a.real()>>a.imag()>>b.real()>>b.imag()>>c.real()>>c.imag()>>d.real()>>d.imag())
	{
		a=a-d; 
		b=b-d; 
		c=c-d;

		double ab=a.real()*b.imag()-a.imag()*b.real();
		double bc=b.real()*c.imag()-b.imag()*c.real();
		double ca=c.real()*a.imag()-c.imag()*a.real();

		if(ab<0&&bc<0&&ca<0) cout<<"YES"<<endl;
		else if(ab>0&&bc>0&&ca>0) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

Measured memory_bytes: 1220
program second
  implicit none
  integer :: n, l, i, k
  integer :: ntas, tas, tas0
  integer, allocatable :: apple(:), absapple(:)
  

  read(*,*) n, l

  allocate(apple(n))
  allocate(absapple(n))

  do i = 1, n
     apple(i) = l + i - 1
     absapple(i) = abs(apple(i))
  end do

  tas0 = minval(absapple)

  ntas = sum(apple)

  do i = 1, n
     if(absapple(i) == tas0) then
        k = i
     end if

  end do

  
  tas = ntas - apple(k)
  write(*,*) tas
end program second



  


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define int long long
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int INF = 1000000000000000000;
const double EPS = 1e-10;
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

vector<int> init(int size){
  vector<int> par(size,-1);
  return par;
}

int root(int x, vector<int>& par){
  if(par[x] < 0){
    return x;
  }else{
    return par[x] = root(par[x],par);
  }
}

bool same(int x, int y, vector<int>& par){
  return root(x, par) == root(y, par);
}

void unite(int x, int y, vector<int>& par){
  x = root(x, par), y = root(y, par);
  if(same(x,y, par))return;
  par[x] += par[y];
  par[y] = x;
}

int size(int x, vector<int>& par){
  return -par[root(x, par)];
}

struct edge { int to, cost; };
vector<edge> gs[210000], gt[210000];
int ds[110000], dt[110000];
int n,m,s,t;

void dijkstra(int s, int d[], vector<edge> g[]){
  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> que;
  fill(d,d+n+1, INF);d[s] = 0;que.push(pair<int,int>(0,s));
  while(!que.empty()){
    pair<int,int> p = que.top();que.pop();
    int v = p.second;
    if(d[v]<p.first)continue;
    rep(i,g[v].size()){
      edge e = g[v][i];
      if(d[e.to] > d[v] + e.cost){
        d[e.to] = d[v] + e.cost;
        que.push(pair<int,int>(d[e.to], e.to));
      }
    }
  }
}

signed main(){
  cin>>n>>m>>s>>t;s--;t--;
  rep(i,m){
    int u,v,a,b;cin>>u>>v>>a>>b;u--;v--;
    gs[u].push_back(edge{v,a});gs[v].push_back(edge{u,a});
    gt[u].push_back(edge{v,b});gt[v].push_back(edge{u,b});
  }
  dijkstra(s,ds,gs);dijkstra(t,dt,gt);
  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> ans;
  rep(i,n)ans.push(make_pair(ds[i] + dt[i], i+1));
  rep(i,n){
    while(ans.top().second <= i)ans.pop();
    cout << 1000000000000000-ans.top().first << endl;
  }
}


Measured memory_bytes: 26164
# include <iostream>

using namespace std;

int main(){
   int N;
   int V[20];
   int C[20];
   int ans = 0;
   cin >> N;
   for(int i=0; i < N; i++){
       cin >> V[i];
   }
   for(int i=0; i < N; i++){
       cin >> C[i];
   }
   for(int i=0; i < N; i++){
       if(V[i] > C[i]) ans += V[i] - C[i];
   }
   cout << ans << endl;
   return 0;
}

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

class Pair {
    final int id;
    final double BMI;

    public Pair( double weight, double height, int id ) {
	this.id = id;
	BMI = weight / ( height * height ) * 10000.0;
    }
}

class Main {

    public static void main(String[] args) {

	final Scanner stdin = new Scanner(System.in);

	while ( true ) {

	    final int n = stdin.nextInt();
	    if ( n == 0 ) {
		break;
	    }

	    Pair maxPair = new Pair(1000000, 1, -1);

	    for ( int i = 0; i < n; i++ ) {
		final int id = stdin.nextInt();
		final int height = stdin.nextInt();
		final int weight = stdin.nextInt();

		final Pair p = new Pair( weight, height, id );
		if ( Math.abs( maxPair.BMI - 22.0 ) > Math.abs( p.BMI - 22.0 ) ) {
		    maxPair = p;
		}		
	    }	    

	    System.out.println( maxPair.id );
	    
	}
	
    }
    
}

Measured memory_bytes: 29636
#include <stdio.h>

int main(void)
{
        char n[3];
        scanf("%s",n);

        for(int i=0;i<2;i++){
                if(n[i]=='9'){
                        printf("Yes\n");
                        return 0;
                }
        }
        printf("No\n");
        return 0;
}


Measured memory_bytes: 1592
N , M = map(int , input().split())
A = [list(map(int,input().split())) for i in range(M)]
tf = [False]*N

for i in range(M):
    A.append(list(reversed(A[i])))

def saiki(aaa):
    ans = 0
    if all(tf) == True:
        return 1
    stack = []
    for i in range(len(A)):
        if A[i][0] == aaa and tf[A[i][1]-1] == False:
            stack.append(A[i][1])

    for i in range(len(stack)):
        tf[stack[i]-1] = True
        ans += saiki(stack[i])
        tf[stack[i]-1] = False
    return ans

def main():
    tf[0] = True
    ans = saiki(1)
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

int main(){
  ll N;
  cin >> N;
  ll A;
  vl wo(N + 1, 0);
  rep2(i, 2, N + 1){
    cin >> A;

    wo[A]++;
  }

  rep2(i, 1, N + 1)
    cout << wo[i] << endl;
  
  return 0;
}


Measured memory_bytes: 4840
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	cout<<S.substr(0,S.size()-8)<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

#define _GLIBCXX_DEBUG
#define all(v) (v).begin(),(v).end()

using namespace std;

using ll=long long;
using pii=pair<int, int>;
using vi=vector<int>;

const ll LINF=1LL<<60;
const int INF=1<<29;
const int MOD=1e9+7;

ll my_pow(ll a, ll n){
    ll res=1;
    while(n > 0){
        if(n & 1) res=res*a;
        a=a*a;
        n>>=1;
    }
    return res;
}

int main(){
    ll H; cin >> H;
    int cnt=0;
    ll res=0;
    while(H > 0){
        res+=my_pow(2LL, (ll)cnt);
        H/=2;
        cnt++;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3556
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
ll dx[4] = { 0, 1, 0, -1 };
ll dy[4] = { 1, 0, -1, 0 };
static const int INF = 1 << 21;
static const int MOD = 1e9 + 7;
static const int MAX = 10000;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n;
vector<pair<int, int>> adj[MAX]; // 重み付き有向グラフの隣接リスト表現

void dijkstra()
{
    priority_queue<pair<int, int>> PQ;
    int color[MAX];
    int d[MAX];
    rep(i, n)
    {
        d[i] = INF;
        color[i] = WHITE;
    }

    d[0] = 0;
    PQ.push(make_pair(0, 0));
    color[0] = GRAY;

    while (!PQ.empty()) {
        pair<int, int> f = PQ.top();
        PQ.pop();
        int u = f.second;

        color[u] = BLACK;

        // 最小値を取り出し,それが最短でなければ無視
        if (d[u] < f.first * (-1)) {
            continue;
        }

        rep(j, adj[u].size())
        {
            int v = adj[u][j].first;
            if (color[v] == BLACK) {
                continue;
            }
            if (d[u] + adj[u][j].second < d[v]) {
                d[v] = d[u] + adj[u][j].second;
                // priority_queueはデフォルトで大きい値を優先するため-1を掛ける
                PQ.push(make_pair(d[v] * (-1), v));
                color[v] = GRAY;
            }
        }
    }

    rep(i, n)
    {
        cout << i << " " << (d[i] == INF ? -1 : d[i]) << endl;
    }
}

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

    int k, u, v, c;
    cin >> n;

    rep(i, n)
    {
        cin >> u >> k;
        rep(j, k)
        {
            cin >> v >> c;
            adj[u].push_back(make_pair(v, c));
        }
    }

    dijkstra();

    return 0;
}


Measured memory_bytes: 8116
#define _CRT_SECURE_NO_WARNINGS
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #define int ll
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define all(c) begin(c), end(c)
#define range(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) range(i,0,b)
#define rangei(i,a,b) for(ll a=a;i<=ll(b);i++)
#define repi(i,b) rangei(i,1,b)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
template<class T> ostream & operator << (ostream &os, vector<T> const &);
template<int n, class...T>
typename enable_if<(n>=sizeof...(T))>::type
_ot(ostream &, tuple<T...> const &){}
template<int n, class...T>
typename enable_if<(n< sizeof...(T))>::type
_ot(ostream &os, tuple<T...> const &t){
    os << (n==0?"":" ") << get<n>(t); _ot<n+1>(os, t);
}
template<class...T>
ostream & operator << (ostream &os, tuple<T...> const &t){
    _ot<0>(os, t); return os;
}
template<class T, class U>
ostream & operator<<(ostream &os, pair<T,U> const &p){
    return os << "(" << p.first << ", " << p.second << ") ";
}
template<class T>
ostream & operator<<(ostream &os, vector<T> const &v){
    rep(i,v.size()) os << v[i] << (i+1==(int)v.size()?"":" "); return os;
}
#ifdef DEBUG
#define dump(...) (cerr << #__VA_ARGS__ << " = " << mt(__VA_ARGS__) \
                   << " [" << __LINE__ << "]" << endl)
#else
#define dump(...)
#endif
void fastios(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#define endl '\n'
}
template<class T>
size_t uniq(vector<T> &v){
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    return v.size();
}
template<class T>
size_t uniq(T *l, size_t n){
    sort(l,l+n);
    return unique(l,l+n) - l;
}
#define mems(arr,val) memset(arr,val,sizeof(arr));
int const mod = 1000000007;
int const inf = numeric_limits<int>::max()/8;

template <class T>
struct FenwickTree {
    int n;
    vector<T> x;
    FenwickTree(int n_ = 0) : n(n_), x(n_+1){
        fill(x.begin(), x.end(), 0);
    }
    T sum(int r){
        int s = 0;
        while (r > 0) {
            s += x[r];
            r -= r & -r;
        }
        return s;
    }
    T sum(int l, int r){
        l++;
        return sum(r) - sum(l-1);
    }
    void add(int i, T a) {
        i++;
        while (i <= n) {
            x[i] += a;
            i += i & -i;
        }
    }
    void set(int k, T a){
        int x = sum(k, k+1);
        add(k, a-x);
    }
    vi to_a(int l = -1, int r = -1){
        if(l == -1) l = 0;
        if(r == -1) r = n;
        vi res(r-l);
        range(i,l,r) res[i-l] = sum(i,i+1);
        return res;
    }
};

int main(){
    fastios();
    int n,q;
    cin >> n >> q;
    FenwickTree<ll> t(n+1);
    rep(i,q){
        int c,x,y;
        cin >> c >> x >> y;
        x--;
        if(c == 0) t.add(x,y);
        else cout << t.sum(x,y) << endl;
    }
}

Measured memory_bytes: 1788
package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scanf("%s", &s)

	if s == "SUN" {
		fmt.Printf("7")
	}
	if s == "MON" {
		fmt.Printf("6")
	}
	if s == "TUE" {
		fmt.Printf("5")
	}
	if s == "WED" {
		fmt.Printf("4")
	}
	if s == "THU" {
		fmt.Printf("3")
	}
	if s == "FRI" {
		fmt.Printf("2")
	}
	if s == "SAT" {
		fmt.Printf("1")
	}
	return
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define e "\n"
#define MaRiaMa { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
#define fix(n) cout << fixed << setprecision(n);
using namespace std;
int ar[1000000];
int arr[1000000];
int main()
{
	MaRiaMa;
	string s;
	cin >> s;
	int k = 0, j = 0;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'A')
		{
			ar[k] = i ;
			k++;
		}
		else if (s[i] == 'Z')
		{
			arr[j] = i ;
			j++;
		}
	}
	cout <<(*max_element(arr,arr+j)-*min_element(ar,ar+k))+1;
}

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

 int main() {
     ll n , m ;
     cin >> n >> m;
     vector<string> v;
     while(n--) {
         string s;
         cin >> s;
         v.push_back(s);
     }
     sort(v.begin(),v.end());
     for (int i = 0; i <v.size() ; ++i) {
         cout<<v[i];
     }
; }

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(ll i = n;i >= 0;--i)
#define FOR(i,m,n) for(ll i = m, i##_len=(n);i <i##_len; ++i)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;
 
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

int main(void)
{
    int n,m;
    cin >> n >> m;
    vector<int> s(m);
    vector<int> c(m);
    REP(i,m){
        cin >> s[i] >> c[i];
    }

    bool exist = true;

    REP(i,m-1){
        FOR(j,i+1,m){
            if(s[i] == s[j] && c[i] != c[j]){
                exist = false;
            }

        }
    }

    if(!exist){
        cout << -1 << endl;
        return 0;
    }

    int zdigit = n + 1;
    int nz = n + 1;
    REP(i, m)
    {
        if(c[i] == 0 && s[i] < zdigit){
            zdigit = s[i];
        }
        else if(c[i] != 0 && s[i] < nz){
            nz = s[i];
        }
    }

    if(zdigit < nz && !(zdigit == n && nz == n+1)){
        cout << -1 << endl;
        return 0;
    }

    if(n == 1 && zdigit == 1 || m == 0 && n == 1){
        cout << 0 << endl;
        return 0;
    }

    vector<int> ans(n,0);
    REP(i,m){
        ans[s[i] - 1] = c[i];
    }
    ans[0] = max(ans[0], 1);
    REP(i,n){
        cout << ans[i];
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
long long n,ans,rema;
vector <long long> a;

int main(){
	cin>>n;
	rema=n;
	for(int i=0;i<n;i++){
		int t;
		cin>>t;
		a.push_back(t);
		ans+=t;
	}
	if(a[0]!=0){
		ans=-1;
	}else{
		for(int i=0;i<n-1;i++){
			if(a[i]+1==a[i+1]){
				ans-=a[i];
			}else if(a[i]+1<a[i+1]){
				ans=-1;
				break;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 2420
n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
x=0
for i in range(n):
    if a[i]>b[i]:
        x+=a[i]-b[i]
    elif a[i]<b[i]:
        x-=(b[i]-a[i])//2
print(["Yes","No"][x>0])

Measured memory_bytes: 41456
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

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

    public void solve(String[] args) {
        MyScanner scanner = new MyScanner();
        int H = scanner.nextInt();
        int W = scanner.nextInt();
        List<String> list = new ArrayList<>();
        for (int i = 0; i < H; i++) {
            list.add(scanner.next());
        }
        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            String s = it.next();
            if (s.indexOf("#") == -1) {
                it.remove();
            }
        }
        for (int i = 0; i < W; i++) {
            boolean f = true;
            for (int j = 0; j < list.size(); j++) {
                String s = list.get(j);
                if (s.charAt(i) == '#') {
                    f = false;
                }
            }
            if (f) {
                for (int j = 0; j < list.size(); j++) {
                    String s = list.get(j);
                    String s2 = s.substring(0,i) + "!" + s.substring(i+1,s.length());
                    list.set(j, s2);
                }
            }
        }

        for (int i = 0; i < list.size(); i++) {
            String s = list.get(i);
            boolean printed = false;
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) != '!') {
                    System.out.print(s.charAt(j));
                    printed = true;
                }
            }
            if (printed) {
                System.out.println();
            }
        }
    }

    private class MyScanner {
        String[] s;int i;BufferedReader br;String reg = " ";
        MyScanner () { s = new String[0];i = 0;br = new BufferedReader(new InputStreamReader(System.in)); }
        public String next() {
            try {
                if (i < s.length) return s[i++]; String line = br.readLine();
                while (line.equals("")) {line = br.readLine();}
                s = line.split(reg, 0); i = 0;return s[i++];
            } catch (Exception e) {e.printStackTrace();}
            return null;
        }
        public int nextInt() {
            try {return Integer.parseInt(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public double nextDouble() {
            try {return Double.parseDouble(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public long nextLong()  {
            try {return Long.parseLong(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
    }
}


Measured memory_bytes: 24276
import numpy as np
import math
import scipy as sp
import queue
import collections

MOD = 10 ** 9 + 7
INF = 10 ** 9

def main(kwargs):
    x = kwargs["x"]
    y = kwargs["y"]
    z = kwargs["z"]

    res = " ".join([z, x, y])
    return res

if __name__ == "__main__":
    kwargs = {}

    cin = input().split()
    #kwargs["n"] = cin[0]
    #kwargs["n"], kwargs["k"] = cin
    #kwargs["n"] = [int(i) for i in cin][0]
    kwargs["x"], kwargs["y"], kwargs["z"] = cin

    cout = main(kwargs)
    print(cout)

Measured memory_bytes: 13460
/**
 * Created by hiramekun at 16:19 on 2019-09-17.
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template<class T>
istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template<class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

void solve() {
    string s;
    cin >> s;
    if (s == "Sunny") {
        cout << "Cloudy" << '\n';
    } else if (s == "Cloudy") cout << "Rainy" << '\n';
    else cout << "Sunny" << '\n';
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
  int N,d[50],i,A,B,C;
  scanf("%d\n",&N);
  for(i=0;i<=N-1;i++){
    scanf("%d",&d[i]);
  }
  
  A=0;
  B=0;
  
  for(i=0;i<=N-1;i++){
    A=A+d[i];
    B=B+(d[i]*d[i]);
  }
  
  A=A*A;
  C=(A-B)/2;
  
  printf("%d",C);
  
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep0(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep1(i,n) for(long long i=1;i<=(long long)(n);i++)
#define all(v) v.begin(),v.end()
#define Sort(v) sort(all(v))
#define Reverse(v) reverse(all(v))
#define Rsort(v) sort(all(v),greater)
#define pub(v) push_back(v)
#define pob(v) pop_back(v)
typedef long long ll;
typedef vector<ll> vel;
typedef vector<vector<ll>> vel2d;
typedef string str;
typedef pair<ll,ll> pal;
typedef vector<str> ves;


int main() {
    ll N,n=1,a=0,b=0;
    cin>>N;
    vel p(N),q(N),f(N);
    rep0(i,N){cin>>p[i];}
    rep0(i,N){cin>>q[i];}
    rep1(i,N){n*=i; f[i-1]=i;}
    vel2d data(n,vel(N));
    ll j=0;
    do{
        data[j]=f;
        j++;
    }while(next_permutation(all(f)));
    rep0(i,n){
        a++;
        if(p==data[i]){break;}
    }
    rep0(i,n){
        b++;
        if(q==data[i]){break;}
    }
    cout<<abs(a-b)<<endl;
}


Measured memory_bytes: 4352
S = input().strip()

while True:
  if S.endswith('dream'):
    S = S[:-5]
  elif S.endswith('dreamer'):
    S = S[:-7]
  elif S.endswith('erase'):
    S = S[:-5]
  elif S.endswith('eraser'):
    S = S[:-6]
  else:
    break

if S:
  print("NO")
else:
  print('YES')

Measured memory_bytes: 3188
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    mixed = False
    for i in range(1, N):
        if A[i] % 2 != A[0] % 2:
            mixed = True
            break
    flag = 0
    if mixed:
        for i in range(N):
            if A[i] % 2 == 1:
                flag = i
                break
    Tentative = [0] * N
    for i in range(N-1):
        Tentative[(flag + i + 1) % N] += A[(flag + i) % N] - Tentative[(flag + i) % N]
        Tentative[(flag + i) % N] *= 2
    Tentative[(flag + N - 1) % N] *= 2
    dam = (Tentative[flag] + Tentative[flag - 1]) // 2
    diff = A[flag - 1] - dam
    if diff != 0:
        for i in range(N//2):
            Tentative[(flag + i) % N] += diff * (-1) ** (i % 2)
            Tentative[(flag - 1 - i) % N] += diff * (-1) ** (i % 2)
        Tentative[(flag + N // 2) % N] += diff * (-1) ** ((N//2) % 2) 

    print(" ".join(map(str, Tentative)))
 
    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 19100
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>E[101000];
int n, Deg[101000], Q[101000], head, tail;
int chk[101000];
int main(){
    int i, a, b, j;
    scanf("%d",&n);
    for(i=1;i<n;i++){
        scanf("%d%d",&a,&b);
        E[a].push_back(b);
        E[b].push_back(a);
        Deg[a]++,Deg[b]++;
    }
    for(i=1;i<=n;i++){
        int c = 0;
        for(j=0;j<E[i].size();j++){
            if(Deg[E[i][j]]==1)c++;
        }
        if(c>=2){
            printf("First\n");
            return 0;
        }
        if(Deg[i]==1)Q[++tail] = i;
    }
    while(head < tail){
        a = Q[++head];
        if(chk[a])continue;
        chk[a] = 1;
        int p = -1;
        for(i=0;i<E[a].size();i++){
            if(!chk[E[a][i]])p = E[a][i];
        }
        chk[p] = 1;
        if(p==-1){
            printf("First\n");
            return 0;
        }
        for(i=0;i<E[p].size();i++){
            Deg[E[p][i]]--;
            if(Deg[E[p][i]]==1){
                Q[++tail] = E[p][i];
            }
        }
    }
    printf("Second\n");
}

Measured memory_bytes: 6912
import sys
from collections import Counter
from itertools import accumulate

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    AC = accumulate([0] + A, func=lambda x,y:(x+y)%M)
    ACC = Counter(AC)

    ans = 0
    for c in ACC.values():
        ans += c * (c-1) // 2
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 15492
#include<cstdio>
#include<cstdlib>
#include<cstring>

struct Node {
    int key;
    Node *prev, *next;
};

Node *nil;

void init() {
    nil = (Node *)malloc(sizeof(Node));
    nil->next = nil;
    nil->prev = nil;
}

void insert(int key) {
    Node *x = (Node *)malloc(sizeof(Node));
    x->key = key;
    x->next = nil->next;
    nil->next->prev = x;
    nil->next = x;
    x->prev = nil;
}

Node* listSearch(int key) {
    Node *cur = nil->next;
    while ( cur != nil && cur->key != key ) {
    	cur = cur->next;
    }
    return cur;
}

void deleteNode(Node *t) {
    if ( t == nil ) return;
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t);
}

void deleteFirst() {
    deleteNode(nil->next);
}

void deleteLast() {
    deleteNode(nil->prev);
}

void deleteKey(int key) {
    deleteNode(listSearch(key));
}

void printList() {
    Node *cur = nil->next;
    int isf = 0;
    while ( 1 ) {
    	if ( cur == nil ) break;
    	if ( isf++ > 0 ) printf(" ");
    	printf("%d", cur->key);
    	cur = cur->next;
    }
    printf("\n");
}

int main() {
    int key, n, i;
    int size = 0;
    char com[20];
    int np = 0, nd = 0;
    scanf("%d", &n);
    init();
    for ( i = 0; i < n; i++ ) {
    	scanf("%s%d", com, &key);
    	if ( com[0] == 'i' ) { insert(key); np++; size++; }
    	else if ( com[0] == 'd' ) {
    		if ( strlen(com) > 6 ) {
    			if ( com[6] == 'F' ) deleteFirst();
    			else if ( com[6] == 'L' ) deleteLast();
    	    }   else {
    	    	deleteKey(key); nd++;
    	    }
    	    size--;
    	}
   }
   
   printList();
   
   return 0;
}


Measured memory_bytes: 33964
from functools import lru_cache
N = input()
K = int(input())

## lru_cacheを使ってメモ化
@lru_cache(maxsize=None)
def rec(k,tight,sum_val):
    # 最後まで探索した時、問題条件に応じて1 or 0を返す
    if k == len(N):
        if sum_val == K and sum_val != 0:
            return 1
        else:
            return 0

    # 現在の桁がtightであるか否かで終了する条件を変更する
    x = int(N[k])
    if tight:
        r = x
    else:
        r = 9
    res = 0
    for i in range(r + 1):
        if i == 0:
            res += rec(k + 1 ,tight and i == r, sum_val)
        else:
            res += rec(k + 1, tight and i == r, sum_val + 1)

    return res



print(rec(0 , True , 0))

Measured memory_bytes: 4832
#include<stdio.h>
#include<string.h>

int main(){
	int n, m, i, j, t, k;
	char a[30];
	while(~scanf("%s", a)){
		char b[26];
		for(i = 0; i < 26; i++)  b[i] = 'a' + i;
		int c[26] = {0};
		int flag = 1;
		getchar();
		int str = strlen(a);
		for(i = 0; i < str; i++){
			for(j = 0; j < 26; j++)
				if(a[i] == b[j]) c[j]++;
		}
		for(i = 0; i < 26; i++)
			if(c[i] >= 2) flag = 0;
		if(flag) printf("yes\n");
		else printf("no\n");
	}
	return 0;
}

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

int main() {
  int a,b,ab;
  cin >> a >> b;
  if(b/10 == 0){
    ab = a*10+b;
  }
  else if(b/100 == 0){
    ab = a*100+b;
  }
  else if(b/100 == 1){
    ab = a*1000+b;
  }
  for(int i = 1;i <= ab;i++){
    if(ab == i*i){
      cout << "Yes" << endl;
      return 0;
    }
    else if(i == ab){
      cout << "No" << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 256
inputA = int(input())

flag = 0
for count in range(inputA,300000):

    for mod in range(2,200000):
        if count % mod == 0:
            flag = mod
            break
        mod += 1
    if count == flag:
        print(count)
        break
    elif flag == 0:
        print(inputA)
    else:
        count += 1


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=200003,INF=1<<30;

ll rui(ll a,ll b){
    ll ans=1;
    while(b>0){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ans;
}

ll comb(ll a,ll b){
    ll ans=1;
    for(ll i=a;i>a-b;i--){
        ans=ans*i%mod;
    }
    for(ll i=1;i<=b;i++){
        ans=(ans*rui(i,mod-2))%mod;
    }
    return ans;
}


int main(){
    
    int X,Y;cin>>X>>Y;
    if((X+Y)%3!=0) cout<<0<<endl;
    else{
        int A=(X+Y)/3;
        X-=A;Y-=A;
        if(X<0||Y<0) cout<<0<<endl;
        else{
            cout<<comb(A,X)<<endl;
        }
    }
}




Measured memory_bytes: 256