akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ll> pdl;
typedef pair<ld, ld> pdd;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
//typedef boost::multiprecision::cpp_int bigint;

ll N, K;
ll points[3];
VLL hands;   //0,1,2->rosk,scisser,paper
VVLL DP;

ll dp(ll n) {
	ll ind = 1;
	DP[0] = { 0,0,0 };
	for (; n < N; n += K,ind++) {
		for (ll h = 0; h < 3; h++) {
			DP[ind][h] = max(DP[ind - 1][(h + 1) % 3], DP[ind - 1][(h + 2) % 3]);
			if ((h + 1) % 3 == hands[n]) {
				DP[ind][h] += points[h];
			}
		}
	}
	ind--;
	return max(DP[ind][0], max(DP[ind][1], DP[ind][2]));
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	cin >> N >> K;
	hands.resize(N);
	cin >> points[0] >> points[1] >> points[2];
	string T;
	cin >> T;
	for (ll n = 0; n < N; n++) {
		if (T[n] == 'r')hands[n] = 0;
		else if (T[n] == 's')hands[n] = 1;
		else hands[n] = 2;
	}
	DP.resize(N+1,VLL(3,0));
	ll ans = 0;
	for (ll n = 0; n < min(N, K); n++) {
		ans += dp(n);
	}
	cout << ans << "\n";
	return 0;
}

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

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


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

  vector<int> l(n);
  for (int i = 0; i < n-1; i++) {
    l[i+1] = gcd(l[i], a[i]);
  }

  vector<int> r(n);
  for (int i = n-1; i >= 1; i--) {
    r[i-1] = gcd(r[i], a[i]);
  }

  int ans = 1;
  for (int i = 0; i < n; i++) {
    ans = max(ans, gcd(l[i], r[i]));
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int N;
 cin >> N;
 //vector<int> tako;
 //cin >> tako;
  vector<int> tako(N);
  for (int i = 0; i < N; i++) {
    cin >> tako.at(i);
  }
  int a=0;
  int b=0;
  int res1 = 0;
  int res2 = 0;
  int sum1 = 0;
  int sum2 =0;

  for(int i=0;i<N;i++){
          a = tako.at(i);
  for(int i=0;i<N;i++){
      b =  tako.at(i);
      res1 = a*b;
	  sum1 = sum1 + res1;	
    }
  }
  for (int i=0;i<N;i++){
          res2 = tako.at(i)*tako.at(i);
    		sum2 = sum2 + res2;
  }
  
  cout << (sum1-sum2)/2;
}

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

int main()
{
	int n,a,b;
	cin>>n>>a>>b;
	
	bool f=true;
	for(int i=a; i<=b; i++)
	{
		if(i%n==0)
		{
			f=true;
			cout<<"OK"<< endl;
			break;
		}
		else
			f=false;
	}
	
	if(f==false)
		cout<<"NG"<< endl;
	
	return 0;
}


Measured memory_bytes: 3632
using System;

namespace ConsoleApp4
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            int count = 0;
            for (int a = 1; a < n; ++a)
            {
                int bmax = n / a;
                for (int b = 1; b <= bmax; ++b)
                {
                    if (a * b < n)
                    {
                        count++;
                    }
                }
            }

            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 27500
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i< (int)(b); ++i)
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
typedef long double ld;
using ll=long long;
using namespace std;
const int mod=1e9+7;
const ll inf = 1LL << 60;
const ld pi = (acos(-1));
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; }


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  
  int n,d; cin >> n >> d;
  cout << (n+2*d)/(2*d+1)<< endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
  int x,arr[4]={0,0,0,0},temp,k=3,i;
  cin >> x;
  while (x>0)
  {
    temp=x%10;
    x=x/10;
    arr[k]=temp;
    k--;
  }
  for(i=0; i<3; i++)
  {
    if(arr[i]==arr[i+1])
    { 
      cout<< "Bad";
      break;
    }
  }
  if(i==3)
  {
    cout<<"Good";
  }
  return 0;
}

Measured memory_bytes: 256
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)    
#define seg_size 524288
int main(){
#define int long long
	string s;
	cin >> s;
	long long a = 0;
	long long b = 0;
	long long c = 0;
	long long casing = 1;
	for (int i = s.length() - 1; i >= 0; --i) {
		if (s[i] == '?') {
			long long tere_a = 0;
			long long tere_b = 0;
			long long tere_c = 0;
			a += b;
			tere_a += a;
			tere_b += b;
			tere_c += c;
			a -= b;
			b += c;
			tere_a += a;
			tere_b += b;
			tere_c += c;
			b -= c;
			c += 1LL*casing;
			tere_a += a;
			tere_b += b;
			tere_c += c;
			c -= 1LL*casing;
			a = tere_a;
			b = tere_b;
			c = tere_c;
			a %= MAX_MOD;
			b %= MAX_MOD;
			c %= MAX_MOD;
			casing *= 3LL;
			casing %= MAX_MOD;
		}
		else if (s[i] == 'A') {
			a += b;
			a %= MAX_MOD;
		}
		else if (s[i] == 'B') {
			b += c;
			b %= MAX_MOD;
		}
		else if (s[i] == 'C') {
			c += 1LL*casing;
			c %= MAX_MOD;
		}
	}
	cout << a%MAX_MOD << endl;
	return 0;
}

Measured memory_bytes: 888
#include<stdio.h>
int main(void)
{
	char a, b, ans;
	scanf("%c %c", &a, &b);
	if (a== 'H')
	{
		if (b == 'H') printf("H\n");
		else if (b == 'D') printf("D\n");
	}
	else if (a== 'D')
	{
		if (b == 'H') printf("D\n");
		else if (b == 'D') printf("H\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <sstream>
#include <algorithm>
#include <set>
#include <deque>
#include <list>
#include <cassert>
#include <iomanip>

using namespace std;

#define in cin
#define out cout
#define ll long long

void output(bool x) {
    if (x) out<<"Yes"<<endl;
    else out<<"No"<<endl;
}

int main() {

    int n;in>>n;
    vector<int> seq(n,0);
    for (int i=0;i<n;i++) in>>seq[i];

    int mini=999999999;
    int maxi=0;

    for (int i=0;i<n;i++) {
        mini=min(mini,seq[i]);
        maxi=max(maxi,seq[i]);
    }


    if (mini==maxi) {
        if (mini==n-1) {output(1);return 0;}
        if (2*mini<=n) {output(1);return 0;}
        output(0);return 0;
    }

    if (mini!=maxi-1) {output(0);return 0;}

    int minc=0;
    int maxc=0;

    for (int i=0;i<n;i++) {
        int a=seq[i];
        assert(seq[i]==mini or seq[i]==maxi);

        if (a==mini) {
            minc++;
        }
        else maxc++;
    }

    if (maxc==1) {output(0);return 0;}

    //MINIDE VÄRVE ON MINC
    //IGA MIN NÄEB MINC-1 VÄRVI
    //SEEGA MAXIDE VÄRVE ON FF=MINI-(MINC-1)=MAXI-MINC
    //SEE SAAB NII OLLA AINULT SIIS KUI FF>=1 JA 2*FF<=MAXC

    int ff=maxi-minc;
    if (ff>=1 and 2*ff<=maxc) {output(1);return 0;}
    else {output(0);return 0;}



    return 0;


}










Measured memory_bytes: 640
#include <bits/stdc++.h> 
#include <vector>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define size_of_array(array) (sizeof(array)/sizeof(array[0]))
using ll =long long;
using namespace std;
using Graph=vector<vector<int>>;
using Field=vector<vector<int>>;

int main(){
    int n;
    cin>>n;
    vector<int> a(n),b(n),c(n-1);
    int ans=0;
    rep(i,n)cin>>a[i];
    rep(i,n){
        cin>>b[i];
        ans+=b[i];
    }
    rep(i,n-1){
        cin>>c[i];
    }
    rep(i,n-1){
        if(a[i]+1==a[i+1])ans+=c[a[i]-1];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3632
n = str(input())
if n[-1] in ['2', '4', '5', '7', '9']:
    how_to_read = 'hon'
elif n[-1] in ['0', '1', '6', '8']:
    how_to_read = 'pon'
else:
    how_to_read = 'bon'
    
print(how_to_read)

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

/*
    全探索でいけそう。
    100個の座標について、N人の体力消費の総和を求め、比較する
    O(100N)

    中央値みたいなのもとめたらもっと早そう
*/

int main() {
    int N;
    cin >> N;

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

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

        long sum = 0;
        for (int j = 0; j < N; j++)
        {
            /* code */
            sum += (i - X[j]) * (i - X[j]);
        }
        ans = min(ans, sum);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = (int)(n-1); i >= 0; i--)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;cin>>s;
  ll n=s.length();
  ll id=0;
  vector<ll>res(n);
  while(1){
    ll r=0,l=0;
    ll li=0;
    while(id<n&&s[id]=='R'){
      r++;
      id++;
    }
    li=id;
    while(id<n&&s[id]=='L'){
      l++;
      id++;
    }
    res[li-1]+=r-r/2+l/2;
    res[li]=r/2+l-l/2;
    if(id==n)break;
  }
  rep(i,n){
    cout<<res[i]<<" ";
  }

  cout<<endl;

  return 0;

}


Measured memory_bytes: 1488
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    V=100005
    n=int(input())
    E=[[] for _ in range(V*2)]
    for _ in range(n):
        x,y=map(int,input().split())
        y+=V
        E[x].append(y)
        E[y].append(x)

    visited=[0]*(2*V)
    def dfs(v):
        if(visited[v]): return
        visited[v]=1
        cnt[v//V]+=1
        for nv in E[v]: dfs(nv)

    ans=[0]
    for v in range(2*V):
        if(visited[v]): continue
        cnt=[0]*2 # 連結成分のx,yの個数
        dfs(v)
        ans[0]+=cnt[0]*cnt[1]
    print(ans[0]-n)
resolve()

Measured memory_bytes: 96816
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <iterator>
#pragma warning(disable:4996)
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
#define MOD 1000000007
using namespace std;

bool solve( long n, long a, long b, long* ans );

bool solve0( long n, long a, long* ans )
{
    if(a==0) { printf("internal error\n"); return false; }

    if(n==1) {
        ans[0]=0; ans[1]=1;
    }
    else {
        long i;
        for(i=0; i<n; i++) {
            if(a & (1<<i)) break;
        }
        if(i==n) { printf("internal error\n"); return false; }

        long j=(i==0? 1: 0);
        if(a==(1<<i)+(1<<j)) {
            return false;
        }

        long j_mod = (j>i? j-1: j);
        if( !solve0( n-1, (1<<j_mod), ans ) ) {
            return false;
        }
        long a_mod = a;
        {
            long m;
            for(m=i; m<n-1; m++) {
                if (a_mod & (1<<(m+1)) ) {
                    a_mod |= (1<<m);
                }
                else {
                    a_mod &= ~(1<<m);
                }
            }
            a_mod &= ~(1<<(n-1));
        }
        if( !solve( n-1, (1<<j_mod), a_mod, ans+(1<<(n-1)) ) ){
            return false;
        }

        // modify
        long m;
        for(m=0; m<(1<<(n-1)); m++) {
            long k;
            for(k=n-1; k>i; k--) {
                if( ans[m] & (1<<(k-1)) ) {
                    ans[m] |= (1<<k);
                }
                else {
                    ans[m] &= ~(1<<k);
                }
            }
            ans[m] &= ~(1<<i);
        }

        for(m=(1<<(n-1)); m<(1<<n); m++) {
            long k;
            for(k=n-1; k>i; k--) {
                if( (ans[m] & (1<<(k-1))) ) {
                    ans[m] |= (1<<k);
                }
                else {
                    ans[m] &= ~(1<<k);
                }
            }
            ans[m] |= (1<<i);
        }        
    }
    return true;
}

bool solve( long n, long a, long b, long* ans )
{
    if( !solve0( n, a^b, ans ) ) {
        return false;
    }

    // modify
    long i;
    for(i=0; i<(1<<n); i++) {
        ans[i] ^= a;
    }
    return true;
}

int main(int argc, char* argv[])
{
    long n, a, b;
    scanf("%ld%ld%ld", &n, &a, &b);

    vector<long> ans(1<<n);
    bool bOk = solve( n, a, b, &(ans[0]) );
    if( bOk ) {
        printf("YES\n");
        long i;
        for(i=0; i<(1<<n); i++) {
            printf("%ld ", ans[i]);
        }
        printf("\n");
    }
    else {
        printf("NO\n");
    }

    return 0;
}


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

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

    ll a;cin>>a;
    string s;cin>>s;

    ll b=0;

    for(int i=0;i<s.size();i++)
    {
        if(s[i] != '.')
        {
            b += (s[i]-'0');
            //cout<<b<<" ";

            b *= 10;
            //cout<<b<<endl<<endl;
        }
    }

    //cout<<b<<endl<<endl;

    b/=10;

    cout<<(a*b)/100<<endl;

    return 0;

}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int a,b,c,k;//testcases
    cin>>a>>b>>c>>k;
    int ans=min(a,k);
    k-=min(a,k);
    if(k>0){
		k-=min(b,k);
		//ans+=min(b,k);
	}
	if(k>0){
		ans-=min(c,k);
		k-=min(c,k);
	}
	cout << ans;
    return 0;
}


Measured memory_bytes: 3652
n,m,a,b,c,d[100010],r,i;
main(){
  while(scanf("%d %d %d %d %d",&n,&a,&b,&c,&m),n){
    for(i=0;i<n;i++)scanf("%d",&d[i]);
    for(i=r=0;i<10001;i++){
      if(d[r]==m)r++;
      if(r==n)break;
      m=(a*m+b)%c;
    }
    printf("%d\n",r-n?-1:i);
  }
return 0;
}

Measured memory_bytes: 604
// 標準入力から一行を読み取り、指定の型に変換する
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

// 標準入力から一行を読み取り、空白文字で分割し、各要素を指定の型に変換する関数
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

use std::cmp::*;

fn main() {
    let n: usize = read();
    let mut b: Vec<u32> = read_vec();
    let mut a: Vec<u32> = vec![0; n];

    a[0] = b[0];

    for i in 1..(n - 1)
    {
        a[i] = min(b[i - 1], b[i]);
    }

    a[n - 1] = b[n - 2];

    println!("{}", a.iter().fold(0, |sum, x| sum + x));
}


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

int main(void){
    int n, a, i, j;
    char w[100][11];

    scanf("%d",&n);
    for(i=0; i<n; i++){
        scanf("%s",w[i]);
    }
    for(i=0; i<n-1; i++){
        a = strlen(w[i]);
        if(w[i][a-1] != w[i+1][0]){
            printf("No\n");
            return 0;
        }
        for(j=i+1; j<n; j++){
            if(strcmp(w[i], w[j]) == 0){
                printf("No\n");
                return 0;
            }
        }
    }
    printf("Yes\n");
    return 0;
}

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

using namespace std;
using ll =long long;
constexpr int mod = 1e9+7;
constexpr int md = mod;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a,b,c;
    cin>>a>>b>>c;
    if((a <= c && b >= c) || (b <= c && a >= c)) cout << "Yes" <<endl;
    else cout << "No" << endl;
    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String s = scan.next();
		char[] s_one = s.toCharArray();
		boolean chain = true;
		int count = 0;

		if(s.equals("RRR")) {
			count = 3;
		}else if(s.equals("RRS") || s.equals("SRR")){
			count = 2;
		}else if(s.equals("RSS") || s.equals("RSR") || s.equals("SSR") || s.equals("SRS")) {
			count = 1;
		}

		System.out.println(count);
	}
}


Measured memory_bytes: 35576
class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in range(n)] #parent[a] = bはaの親がbであることを示す。最初はすべてroot。
        self.rank = [0] * (n+1) # 根の深さ
        self.cnt = 0


    def root(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]


    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


    def groupsize(self):
        self.cnt = 0
        for i, x in enumerate(self.parent):
            if x == i:
                self.cnt += 1
        return self.cnt


N, M = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
uf = UnionFind(N)

for i in range(M):
    uf.unite(A[i][0]-1, A[i][1]-1)

print(uf.groupsize())

Measured memory_bytes: 32384
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass
{
    static void Main()
    {
        int n = int.Parse(ReadLine());
        var a = ReadLine().Split().Select(long.Parse).ToArray();

        
        long ans = 0;
        long sum = 0;
        bool sign = false;
        for (int i = 0; i < n; i++)
        {
            sum += a[i];
            if (sign && sum <=0)
            {
                ans += Abs(sum) + 1;
                sum = 1;
            }
            else if (!sign && sum >= 0)
            {
                ans += Abs(sum) + 1;
                sum = -1;
            }
            sign = !sign;
        }

        long ans2 = 0;
        sum = 0;
        sign = true;
        for (int i = 0; i < n; i++)
        {
            sum += a[i];
            if (sign && sum <= 0)
            {
                ans2 += Abs(sum) + 1;
                sum = 1;
            }
            else if (!sign && sum >= 0)
            {
                ans2 += Abs(sum) + 1;
                sum = -1;
            }
            sign = !sign;
        }
        WriteLine(Min(ans,ans2));
    }
}


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

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;

int main(){
	
	FASTIO
	
	double d, t, s;
	cin >> d >> t >> s;
	cout << ((d/s > t) ? "No\n" : "Yes\n");

	return 0;
}

Measured memory_bytes: 3696
import math

N = int(input())

a=N%100
b=N//100

x=a//5
y=a%5

if y ==4:
  x+=2
elif y==3 or y==2 or y==1:
  x+=1

#print(b,x)
if b>=x:
  print("1")
else:
  print("0")

Measured memory_bytes: 3060
#include <stdio.h>
int main() {int N,i,j,a,b,A[105][105],mx;for (scanf("%d",&N),i=0;i<N;i++) for (j=0;j<N;scanf("%d",&A[i][j++]));mx=A[0][0];
	for (i=1;i<N;A[i][0]+=A[i-1][0],A[0][i]+=A[0][i-1],i++);for (i=1;i<N;i++) for (j=1;j<N;A[i][j]+=A[i-1][j]+A[i][j-1]-A[i-1][j-1],j++);
	for (i=-1;i<N;i++) for (j=-1;j<N;j++) for (a=i+1;a<N;a++) for (b=j+1;b<N;b++) {int k=A[a][b]+((i>-1 && j>-1)?A[i][j]:0)-((i>-1)?A[i][b]:0)-((j>-1)?A[a][j]:0);if (mx<k) mx=k;} printf("%d\n",mx);return 0;}

Measured memory_bytes: 1072
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<iomanip>
#define pi 3.14159265358979323846
#define ll long long
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
int main(){
  int x, a, b;
  cin >> x >> a >> b;
  if(a >= b){
    cout << "delicious\n";
    return 0;
  }
  b -= a;
  if(b <= x){
    cout << "safe\n";
    return 0;
  }
  cout << "dangerous\n";
}
           

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
int main() {
    int N,Q;
    cin >> N >> Q;
    dsu uf(N);
    while(Q--) {
        int t,u,v;
        cin >> t >> u >> v;
        if(t == 0) {
            uf.merge(u,v);
        }
        else {
            cout << uf.same(u,v) << endl;
        }
    }
}


Measured memory_bytes: 4012
// In the name of God

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	double n;
	cin >> n;
	for(int i=1;i<=1e7;i++) {
		if( (i*108)/100 == n) {
			cout << i;
			exit(0);
		}
	}
	cout << ":(";
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1000000007;
using Graph = vector<vector<int>>;

signed main() {
  
  int N, K;
  cin >> N >> K;
  vector<int> V(N);
  for( int i = 0; i < N; i++ ) cin >> V.at(i);
  
  int ans = 0;
  for( int l = 0; l <= min(N, K); l++ ){
    for( int r = 0; l+r <= min(N, K); r++ ){
      priority_queue<int, vector<int>, greater<int>> pq;
      int total = 0;
      for( int i = 0; i < l; i++ ){
        pq.push(V.at(i));
        total += V.at(i);
      }
      for( int i = 0; i < r; i++ ){
        pq.push(V.at(N-i-1));
        total += V.at(N-i-1);
      }
      for( int s = l+r; s < K; s++ ){
        if( !pq.empty() && pq.top() < 0 ){
          total -= pq.top();
          pq.pop();
        }
      }
      ans = max(ans, total);
    }
  }
  
  cout << ans << endl;
  
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using ll = long long;

using namespace std;

#define LOG_MAX 30
// 1つ先が無い(木の根など)場合、値を負かn以上とする
template <typename T>
class Doubling {
    const size_t n;
    vector<vector<T>> next;
public:
    Doubling() {}
    Doubling(vector<T> first_row) 
    : n(first_row.size()), 
      next(LOG_MAX, vector<T>(n)) {
        copy(first_row.begin(), first_row.end(), next[0].begin());
        for (size_t i=1; i<LOG_MAX; i++) {
            for (size_t j=0; j<n; j++) {
                next[i][j] = (
                    (0 <= next[i-1][j] && (size_t)next[i-1][j] < n)
                    ? next[i-1][(size_t)next[i-1][j]]
                    : next[i-1][j]
                );
            }
        }
    }

    // iからstep回移動して到達できる場所をO(log(n))で返す
    T n_step(T i, int step=1) {
        for (int k=LOG_MAX-1; k>=0; k--) {
            if ((step >> k) & 1) i = next[(size_t)k][(size_t)i];
            if (i < 0 || n <= (size_t)i) break;
        }
        return i;
    }

    // 任意のi, sについて next[s][i] >= i or next[s][i] == -1
    // が成り立つ時のみ使用可能
    // iからj(jからi)に行くまでの距離をO(log(n))で計算
    T dist(T i, T j) {
        if (i > j) swap(i, j);
        int d = 0;
        for (int k=LOG_MAX-1; k>=0 && i < j; k--) {
            if (next[k][i] < j) {
                i = next[k][i];
                d += (1 << k);
            }
        }
        return d + 1;
    }
};

int main() {
    int n, q;
    cin >> n;
    long x[n], l;
    for (auto &xi:x) cin >> xi;
    cin >> l >> q;
    vector<int> first_row(n);
    for (int i=0; i<n; i++) {
        int ub = upper_bound(x+i, x+n, x[i] + l) - x;
        first_row[i] = ub - 1;
    }
    Doubling<int> db(first_row);
    for (int i=0, a, b; i<q; i++) {
        cin >> a >> b;
        a--; b--;
        cout << db.dist(a, b) << '\n';
    }
    return 0;
}


Measured memory_bytes: 13952
int_s = gets.to_i
s_arr = gets.split(" ").map(&:to_i).uniq
int_t = gets.to_i
t_arr = gets.split(" ").map(&:to_i).uniq

count = 0
s_arr.each do |val1|
  t_arr.each do |val2|
    count += 1 if val1 == val2
  end
  t_arr
end

puts count

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

int main() {
  int N;
  cin >> N;
  
  vector<int> A(N+1);
  
  for (int i = 0; i < N; i++) {
    cin >> A.at(i+1);
  }
  
  int p = 1;
  int r = 0;
  
  while (p != 2) {
    if (r > N - 1) {
      r = -1;
      break;
    }
    p = A.at(p);
    r += 1;
  }
  
  cout << r << endl;
}

Measured memory_bytes: 3788
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int N, K;
int mindx, maxdx;
int count = 0;
long t;
int main(){
    cin >> N >> K;
    vector<long> n(N);
    for (int i =0; i< N; i++){
        cin >> n[i];
    }
    long r = 10000000000;
    sort(n.begin(), n.end());
    for (int i = 0; i < N - K + 1; i++){
        r = min(r,n[i+K - 1] - n[i]);
    }
    cout << r;
}

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

int sc[26], tc[26];

int main(){
	string s, t;
	cin >> s >> t;
	
	for(int i=0; i<26; i++){
		sc[i] = -1;
		tc[i] = -1;
	}
	
	bool flag = true;
	for(int i=0; i<s.size(); i++){
		int si = s[i] - 'a', ti = t[i] - 'a';
		if(sc[si] < 0) sc[si] = ti;
		else if(sc[si] != ti) flag = false;
		if(tc[ti] < 0) tc[ti] = si;
		else if(tc[ti] != si) flag = false;
	}
	
	if(flag) cout << "Yes" << endl;
	else cout << "No" << endl;
	
	
	return 0;
}

Measured memory_bytes: 776
#include <iostream>
#include <string>
#include <stack>
#include <cstdlib>
#include <cstdio>
using namespace std;
stack <int> st;

int solve(string str){
  int b = st.top(); st.pop();
  int a = st.top(); st.pop();
  if(str=="+")return a+b;
  else if(str=="-")return a-b;
  else if(str=="*")return a*b;
  else if(str=="/")return a/b;
}

int main(){
  string str;
  while(cin>>str){
    if(str=="+"||str=="-"||str=="*"||str=="/")
      st.push(solve(str));
    else st.push(atoi(str.c_str()));
    if(getchar()=='\n'){
      cout << st.top() << endl;
      return 0;
    }
  }
}



Measured memory_bytes: 3172
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <cassert>
#include <string>
#include <cmath>
#include <iomanip>

using namespace std;
using ll = long long;
using ld = long double;

#define st first
#define nd second

const int MAXN = 4e2 + 5, inf = 1e9;
const ll INF = 1e18, mod = 1e9 + 7;
const ld PI = 3.1415926535897932384626433832795;

int cnt[MAXN];
ll dp[MAXN][MAXN], p[MAXN], a[MAXN], sum[MAXN];
bool vis[MAXN], used[MAXN];

vector<int> G[MAXN];
vector<ll> V;
set<ll> S;
map<ll, int> M;
stack<ll> St;
queue<ll> Q;

ll Sum(int a, int b) {
    if (a <= 0) {
        return sum[b];
    }
    return sum[b] - sum[a - 1];
}

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

    //////////////////////////////////////////
    //////////////////////////////////////////

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }

    for (int len = 1; len <= n; len++) {
        for (int i = 1; i + len <= n; i++) {
            int j = i + len;
            dp[i][j] = INF;
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + Sum(i, j));
            }
        }
    }
    cout << dp[1][n] << "\n";
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define pb push_back
#define pf pop_front
#define mp make_pair
#define mod 1000000007
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mat vector<vector<int>>
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define fo(i,n) for(int i=0;i<n;i++)
#define inp(a) int a;cin>>a;
#define inpa(a,n)vector<int> a(n);fo(i,n)cin>>a[i];
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
using namespace std;
#define int ll


auto max(auto a){auto ans=a[0];for(auto i:a)if(i>ans)ans=i;return ans;}
auto min(auto a){auto ans=a[0];for(auto i:a)if(i<ans)ans=i;return ans;}
void print(auto a){for(auto i:a)cerr<<i<<' ';cerr<<'\n';}

int n,m;
vector<vector<int>> conn,dist;
vector<bool> done;

void dfs(int node,int d)
{
	done[node]=1;
	queue<pair<int,int>> q;
	q.push({node,d});
	while(q.size())
	{
		int curr=q.front().F;
		int dst=q.front().S;
		dist[node][curr]=dst;
		q.pop();
		for(int i:conn[curr])
		{
			if(!done[i])
			{
				done[i]=1;
				q.push({i,dst+1});
			}
		}
	}
}



signed main()
{
	fio
	cin>>n>>m;
	conn.resize(n);
	dist.resize(n,vector<int>(n,1001));
	fo(i,m)
	{
		inp(x) inp(y)
		x--,y--;
		conn[x].pb(y);
	}
	fo(i,n)
	{
		done=vector<bool>(n);
		dfs(i,0);
	}
	int fans=1001;
	pair<int,int> ans;
	fo(i,n)
	{
		for(int j=i+1;j<n;j++)
		{
			if(dist[i][j]+dist[j][i]<fans)
			{
				fans=dist[i][j]+dist[j][i];
				ans={i,j};
			}
		}
	}
	if(fans==1001)
	{
		cout<<-1<<'\n';
	}
	else
	{
		vector<int> ffans;
		int curr=ans.F;
		int dst=dist[ans.F][ans.S];
		while(curr!=ans.S)
		{
			for(int i:conn[curr])
			{
				if(dist[i][ans.S]==dst-1)
				{
					ffans.pb(i);
					curr=i;
					dst--;
					break;
				}
			}
		}
		curr=ans.S;
		dst=dist[ans.S][ans.F];
		while(curr!=ans.F)
		{
			for(int i:conn[curr])
			{
				if(dist[i][ans.F]==dst-1)
				{
					ffans.pb(i);
					curr=i;
					dst--;
					break;
				}
			}
		}
		cout<<ffans.size()<<'\n';
	for(int i:ffans)
		cout<<i+1<<'\n';
	}
	printclock;
}

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

int main(){
    int a; cin>>a;
  if(a<105){
    cout<<0;}
  else if(a<135){
    cout<<1;}
  else if(a<165){
    cout<<2;}
  else if(a<189){
    cout<<3;}
  else if(a<195){
    cout<<4;}
  else{
    cout<<5;}
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
template <typename T> using posteriority_queue = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
template <typename T> void unique(vector<T> &a) { a.erase(unique(ALL(a)), a.end()); }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

int main() {
  int a, b, c; cin >> a >> b >> c;
  set<int> ans{a, b, c};
  cout << ans.size() << '\n';
  return 0;
}


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

const int maxn = 1 << 18;

const int mod = 998244353;
inline int sum(int x, int y) { return (x+(long long)y) % mod; }
inline int sub(int x, int y) { return sum(x, mod-y); }
inline int mul(int x, int y) { return (x*(long long)y) % mod; }
inline int power(int x, int y) {
    int ans = 1;
    for (int i=0; i<31; i++, x=mul(x, x)) if ((y>>i)&1) ans = mul(ans, x);
    return ans;
}

struct segt {
    int t[maxn*2];
    int merge(int a, int b) { return sum(a, b); }
    void update(int s, int e, int x, int p, int v) {
        if (s==e) t[x] = v;
        else {
            int m = (s+e)/2;
            if (p<=m) update(s, m, 2*x, p, v);
            else update(m+1, e, 2*x+1, p, v);
            t[x] = merge(t[2*x], t[2*x+1]);
        }
    }
    void update(int p, int v) { return update(0, maxn-1, 1, p, v); }
    int query(int s, int e, int x, int l, int r) {
        if (l<=s and e<=r) return t[x];
        else if (l<=e and s<=r) {
            int m = (s+e)/2;
            return merge(query(s, m, 2*x, l, r), query(m+1, e, 2*x+1, l, r));
        } else return 0;
    }
    int query(int l, int r) { return query(0, maxn-1, 1, l, r); }
} t;

int N, K, l[maxn], r[maxn], dp[maxn];

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

	cin >> N >> K;
	for (int i=0; i<K; i++) cin >> l[i] >> r[i];

	dp[1] = 1;
	t.update(1, 1);

	for (int i=2; i<=N; i++) {
		for (int k=0; k<K; k++) dp[i] = sum(dp[i], t.query(i-r[k], i-l[k]));
		t.update(i, dp[i]);
	}

	cout << dp[N] << '\n';
}

Measured memory_bytes: 6096
//==========================================================================
//
//                   Bismillahir-Rahmanir-Rahim
//
// ==========================================================================
#include <bits/stdc++.h>
#define        ll                              long long int
#define        f(x,y,z)                        for(int x=y;x<z;x++)
#define        pii                             pair<int,int>
#define        pll                             pair<ll,ll>
#define        CLR(a)                          memset(a,0,sizeof(a))
#define        SET(a)                          memset(a,-1,sizeof(a))
#define        N                               100010
#define        M                               1000000007
#define        pi                              acos(-1.0)
#define        ff                              first
#define        ss                              second
#define        pb                              push_back
#define        inf                             (int)1e9
#define        eps                              1e-9
using namespace std;
int dx[]={0,0,1,-1,-1,-1,1,1};
int dy[]={1,-1,0,0,-1,1,1,-1};
template < class T> inline T biton(T n,T pos){return n |((T)1<<pos);}
template < class T> inline T bitoff(T n,T pos){return n & ~((T)1<<pos);}
template < class T> inline T ison(T n,T pos){return (bool)(n & ((T)1<<pos));}
template < class T> inline T gcd(T a, T b){while(b){a%=b;swap(a,b);}return a;}
template <typename T> string NumberToString ( T Number ) { ostringstream ss; ss << Number; return ss.str(); }
inline int nxt(){int aaa;scanf("%d",&aaa);return aaa;}
inline ll lxt(){ll aaa;scanf("%lld",&aaa);return aaa;}
inline double dxt(){double aaa;scanf("%lf",&aaa);return aaa;}
template <class T> inline T bigmod(T p,T e,T m){T ret = 1;
for(; e > 0; e >>= 1){
    if(e & 1) ret = (ret * p) % m;p = (p * p) % m;
} return (T)ret;}
#define sayed
#ifdef sayed
     #define debug(args...) {cerr<<"Debug: "; dbg,args; cerr<<endl;}
#else
    #define debug(args...)  // Just strip off all debug tokens
#endif
struct debugger{
    template<typename T> debugger& operator , (const T& v){
        cerr<<v<<" ";
        return *this;
    }
}dbg;
///******************************************START******************************************
vector<string> v;
int main(){
     //freopen("out.txt","w",stdout);
    //ios_base::sync_with_stdio(false);
   //cin.tie(0);
   string s;
   cin>>s;
    s+=',';
    string temp;
   for(int i=0;i<s.length();i++){
        if(s[i]==','){
              v.pb(temp);
              temp.clear();
              continue;
        }
        temp+=s[i];
   }
   for(int i=0;i<v.size();i++){
      if(i) cout<<" ";
      cout<<v[i];
   }
   cout<<endl;

return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define MD 1000000007
#define INF 1000000000
#define M_INF -1000000000
typedef long long int ll;

int main(){
    int N;
    cin>>N;
    vector<int> x(N),y(N),h(N);
    for(int i=0;i<N;i++){
        cin>>x[i]>>y[i]>>h[i];
    }
    
    for(int i=0;i<=100;i++){//y座標
        for(int j=0;j<=100;j++){//x座標
        int ans_h=-1;
            for(int k=0;k<N;k++){
                if(h[k]>0){
                    if(ans_h==-1){
                        ans_h=h[k]+abs(j-x[k])+abs(i-y[k]);
                    }else{
                        int tmp_h=h[k]+abs(j-x[k])+abs(i-y[k]);
                        if(ans_h!=tmp_h){
                            ans_h=-2;
                            break;
                        }
                    }
                }
            }
            for(int k=0;k<N;k++){
                if(ans_h==-2){
                    break;
                }else if(h[k]==0){
                    int tmp_h=abs(j-x[k])+abs(i-y[k]);
                    if(ans_h>tmp_h){
                        ans_h=-2;
                        break;
                    }
                }
            }
            if(ans_h==-2){
                continue;
            }else{
                cout<<j<<' '<<i<<' '<<ans_h<<endl;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define enld endl //* missspell check
const ll INF = 1LL << 60;


void solve(long long H, long long W, std::vector<std::string> S){
    vector<vll> dp(H + 1, vll(W + 1, INF));
    if(S[0][0]=='#') dp[0][0] = 1;
    else dp[0][0] = 0;
    REP(x, H) REP(y, W){
        if(x > 0) {
            if(S[x][y]=='#' && S[x - 1][y]=='.')  dp[x][y] = min(dp[x][y], dp[x - 1][y] + 1);
            else dp[x][y] = min(dp[x][y], dp[x - 1][y]);
        }
        if(y > 0) {
            if(S[x][y]=='#' && S[x][y - 1]=='.')  dp[x][y] = min(dp[x][y], dp[x][y - 1] + 1);
            else dp[x][y] = min(dp[x][y], dp[x][y - 1]);
        }
    }
    cout << dp[H - 1][W - 1] << endl;

}

int main(){
    long long H;
    scanf("%lld",&H);
    long long W;
    scanf("%lld",&W);
    std::vector<std::string> S(H);
    for(int i = 0 ; i < H ; i++){
        std::cin >> S[i];
    }
    solve(H, W, std::move(S));
    return 0;
}


Measured memory_bytes: 384
import java.util.*;

public class Main {

	void insertionSort(int[] A) {
		for (int i = 1; i < A.length; i++) {
			int v = A[i];
			int j = i - 1;
			while (j >= 0 && A[j] > v) {
				A[j+1] = A[j];
				j--;
			}
			A[j+1] = v;
			printArray(A);
		}
	}

	void printArray(int[] A) {
		System.out.print(A[0]);
		for (int i = 1; i < A.length; i++) {
			System.out.print(" " + A[i]);
		}
		System.out.println();
	}

	void run() {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] A = new int[n];
		for (int i = 0; i < A.length; i++) {
			A[i] = scan.nextInt();
		}
		printArray(A);
		insertionSort(A);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main().run();
	}

}



Measured memory_bytes: 30732
#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define  FI first
#define  SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl; 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 2e5+10;
// double a[maxn];

vector<int > G[maxn];

LL V[maxn];
void dfs(int u,int fa){
    for(int i = 0;i < G[u].size(); ++i){
        int c= G[u][i];
        if(c == fa) continue;
        V[c] += V[u];
        dfs(c,u);
    }
}
int main(void)
{
    int n,Q;cin>>n>>Q;
    for(int i = 0;i < n-1; ++i){
        int u,v;scanf("%d%d",&u,&v);
        G[u].Pb(v);
        G[v].Pb(u);
    }    
    while(Q--){
        int p,x;
        scanf("%d%d",&p,&x);
        V[p]+=x;
    }
    dfs(1,-1);
    for(int i = 1;i <= n;++i)
        printf("%lld  ",V[i]);

   return 0;
}

Measured memory_bytes: 24448
#include <stdio.h>
#include <limits.h>
#include <algorithm>
 
using namespace std;
 
int cmp_count = 0;
 
 
void merge(int A[],int left,int mid, int right){
    int n1 = mid - left;
    int n2 = right - mid;
    int L[n1+1],R[n2+1];
    for(int i = 0; i < n1; i++) L[i] = A[left + i];
    for(int i = 0; i < n2; i++) R[i] = A[mid + i];
    L[n1] = R[n2] =  INT_MAX;
 
    int i = 0, j = 0;
    for(int k = left;k < right; k++){
        if(L[i] <= R[j]){
            A[k] = L[i++];
            cmp_count++;
        }else{
            A[k] = R[j++];
            cmp_count++;
        }
    }
}
 
void mergeSort(int A[],int left,int right){
    if(left+1 < right){
        int mid = (left+right)/2;
        mergeSort(A,left,mid);
        mergeSort(A,mid,right);
        merge(A,left,mid,right);
    }
}
 
int main(){
    int n;
    scanf("%d",&n);
    int S[n];
    for(int i = 0; i < n; i++) scanf("%d",&S[i]);
 
    mergeSort(S,0,n);
 
    for(int i = 0; i < n-1; i++) printf("%d ",S[i]);
    printf("%d\n",S[n-1]);
    printf("%d\n",cmp_count);
 
}


Measured memory_bytes: 6620
#include<bits/stdc++.h>
#define ll long long int
#define mod 998244353
#define ld long double
using namespace std;
int main(void){
	int i,n,j,s;
	cin>>n>>s;
	int a[n];
	for(i=0;i<n;i++)
	cin>>a[i];
	ll dp[n+1][s+1];
	memset(dp,0,sizeof dp);
	dp[0][0]=1;
	for(i=0;i<n;i++){
		for(j=0;j<=s;j++){
			dp[i+1][j]+=2*dp[i][j];
			dp[i+1][j]%=mod;
			if(a[i]+j<=s){
				dp[i+1][j+a[i]]+=dp[i][j];
				dp[i+1][j+a[i]]%=mod;
			}
		}
	}
	cout<<dp[n][s]<<endl;
}


Measured memory_bytes: 73996
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

int N,M;
Int A[100000+10];

int main(void) {
    cin>>N>>M;

    for(int i = 0;i < M;i++) {
        int a;
        cin>>a;
        A[a] = -1;
    }

    if(A[1] != -1) {
        A[1] = 1;
    }
    A[0] = 1;
    for(int i = 2;i <= N;i++) {
        if(A[i] == -1)
            continue;

        if(A[i-1] != -1) {
            A[i] += A[i-1];
            A[i] %= MOD;
        }
        if(A[i-2] != -1) {
            A[i] += A[i-2];
            A[i] %= MOD;
        }
    }

    cout<<A[N]<<endl;

    return 0;
}


Measured memory_bytes: 1024
import sys 
x,y,A,B,C=map(int,sys.stdin.readline().split())
R=list(map(int,sys.stdin.readline().split()))
G=list(map(int,sys.stdin.readline().split()))
N=list(map(int,sys.stdin.readline().split()))
arr=[]
for i in range(A):
    arr.append([R[i],-1])
for i in range(B):
    arr.append([G[i],-2]) 
for i in range(C):
    arr.append([N[i],-3])    
arr.sort(reverse=True)
ans=0
adv=0
for i in range(len(arr)):
    if x+y==adv:
        break
    if arr[i][1]==-1:
        if x>0:
            ans+=arr[i][0]
            x-=1 
    elif arr[i][1]==-2:
        if y>0:    
            ans+=arr[i][0]
            y-=1
    else:
        ans+=arr[i][0]
        adv+=1 
        
print(ans)        

Measured memory_bytes: 126956
// AtCoder165 C

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <string.h>
#include <memory.h>
#include <malloc.h>
#include <stdlib.h>

// qsortで用いる比較用関数．*a<*bならaが先になる．
int compare(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}


int main() {
    int i,j;
    int n;
    int k;
    int* x;
    int sum = 0;

    scanf("%d", &n);
    scanf("%d", &k);
    x = (int*)malloc(sizeof(int) * n);
    for(i=0;i<n;i++){
        scanf("%d", x+i);
        if(k/2 < *(x+i)){
            sum += abs(*(x+i)-k);
        }else{
            sum += *(x+i);
        }
    }

    sum *= 2;
    printf("%d", sum);

    return 0;
}

Measured memory_bytes: 128
import java.util.*;
import java.math.*;
class Main{
  public static void main(String args[])
  {
    Scanner in=new Scanner(System.in);
    double a=in.nextDouble();
    double b=in.nextDouble();
    double n=in.nextDouble();
    if(n<b)
    {
      double x=Math.floor((a*n)/b);
      System.out.print((int)x);
    }
    if(n>=b )
    {
      
      n=b-1;
      double x=Math.floor((a*n)/b);
      System.out.print((int)x);
    }
  
    else if(n==1)
    {
      double v=Math.floor((a*n)/b)-a*Math.floor(n/b);
       System.out.print((int)v);
    }
    
    
  }
}


Measured memory_bytes: 37308
#include<bits/stdc++.h>
#define N 400005
using namespace std;
int n,a[N],b[N];
bool ok(int x)
{
	int i;
	for(i=1;i<2*n;i++) b[i]=(a[i]>x);
	for(i=1;i<n;i++){
		if(b[n+i]==b[n+i-1]) return b[n+i];
		if(b[n-i]==b[n-i+1]) return b[n-i];
	  }
	return b[n]^(~n&1);
}
int main()
{
	int i,l,r,mid;
	scanf("%d",&n);
	for(i=1;i<2*n;i++)
		scanf("%d",&a[i]);
	l=0,r=2*n-1;
	while(r-l>1){
		mid=(l+r)>>1;
		if(ok(mid)) l=mid;
		else r=mid;
	  }
	cout<<r;
	return 0;
}


Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;cin>>n;
  int k;cin>>k;
  vector<int>a(n+1);
  int flag=0;
  for(int i=1;i<=n;i++){
    cin>>a.at(i);
    if(i<=k&&a.at(i)==0)flag++;
  }
  for(int i=k+1;i<=n;i++){
    if(flag==1){
      if(a.at(i-k)==0&&a.at(i)!=0){
        cout<<"Yes"<<endl;
        flag--;
        continue;
      }
      else{
        cout <<"No"<<endl;
        if(a.at(i-k)==0)flag--;
        if(a.at(i)==0)flag++;
        continue;
      }
    }
    else if(flag==0){
      if(a.at(i-k)<a.at(i)){
        cout <<"Yes"<<endl;
        continue;
      }
      else{
        cout <<"No"<<endl;
        if(a.at(i)==0)flag++;
        continue;
      }
    }
    else{
      cout<<"No"<<endl;
      if(a.at(i-k)==0)flag--;
      if(a.at(i)==0)flag++;
      continue;
    }
  }
  cout <<endl;
}

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

#define FOR(s, i, n) for(int i = s; i n; i++)
typedef long long ll;
const int INF = 1e9;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	string s;
	cin>>s;
	for (char a:s){
		if (a == '?'){
			cout<<"D";
		}else{
			cout<<a;
		}
	}
	cout<<'\n';
	return 0;
}

Measured memory_bytes: 3788
use std::io;

fn main() {
    let mut line = String::new();
    io::stdin().read_line(&mut line).ok();
    let s = line.trim();
    let s = s.to_string() + s;

    let mut line = String::new();
    io::stdin().read_line(&mut line).ok();
    let p = line.trim();

    match s.find(p) {
        Some(_) => println!("Yes"),
        None    => println!("No"),
    }
}



Measured memory_bytes: 5036
#include <bits/stdc++.h>
#include <atcoder/all>

#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)

using namespace std;
using namespace atcoder;

using ll = long long;
using P = pair<int, int>;

int main() {
  int n, m;
  cin >> n >> m;
  dsu uf(n);
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    uf.merge(a, b);
  }
  int res = uf.groups().size() - 1;
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 8948