akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>

constexpr int MAX_XY = 1010;

int lx, ly, q, dp[MAX_XY][MAX_XY];
std::string sx, sy;

void fill_dp(){
    for(int i = 1; i <= lx; ++i){
        for(int j = 1; j <= ly; ++j){
            if(sx[i - 1] == sy[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
}

void solve(){
    fill_dp();
    std::cout << dp[lx][ly] << std::endl;
    return;
}

int main(){
    std::cin >> q;
    
    for(int i = 0; i < q; ++i){
        std::cin >> sx >> sy;
        lx = sx.size(), ly = sy.size();
        solve();
    }
    return 0;
}

Measured memory_bytes: 7072
#[allow(unused_imports)]
use std::cmp::Ordering;

#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};

#[allow(unused_imports)]
use std::iter::FromIterator;

#[allow(unused_macros)]
macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::min($x, min!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::max($x, max!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! get {
    ([$t: ty]) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    };
    ([$t: ty];$n: expr) => {
        (0..$n).map(|_|get!([$t])).collect::<Vec<_>>()
    };
    ($t: ty) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t: ty),*) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*)
        }
    };
    ($t: ty; $n: expr) => {
        (0..$n).map(|_|get!($t)).collect::<Vec<_>>()
    };
    ($($t: ty),*; $n: expr) => {
        (0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*).unwrap();
    }
}

const BIG_STACK_SIZE: bool = true;

#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}

fn solve() {
    let n = get!(usize);
    let a = get!([isize]);

    let mut before = vec![BTreeMap::new(); 2];
    before[0].insert(0, 0);
    for i in 0..n {
        let mut new = vec![BTreeMap::new(); 2];
        for (&k, &v) in &before[0] {
            if (i > 0 && (i - 1) / 2 > k) || (i + 1) / 2 < k {
                continue;
            }
            let entry = new[0].entry(k).or_insert(v);
            *entry = max!(*entry, v);
            let entry = new[1].entry(k + 1).or_insert(v + a[i]);
            *entry = max!(*entry, v + a[i]);
        }

        for (&k, &v) in &before[1] {
            if (i > 0 && (i - 1) / 2 > k) || (i + 1) / 2 < k {
                continue;
            }
            let entry = new[0].entry(k).or_insert(v);
            *entry = max!(*entry, v);
        }
        before = new;
    }

    let mut mx = std::isize::MIN;
    for i in 0..2 {
        mx = max!(mx, before[i].get(&(n / 2)).cloned().unwrap());
    }
    println!("{}", mx);
}


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

int main() {
  int N;
  cin >> N;
  vector<ll> H(N);
  for (int i = 0; i < N; i++) {
    cin >> H[i];
  }
  ll cnt = 0;
  for (int i = 0; i < N-1; i++) {
    if (H[i] == H[i+1]) {
      cnt++;
      continue;
    }
    if (H[i] > H[i+1]) {
      for (int j = i; j >= i-cnt; j--) {
        H[j]--;
      }
    }
    cnt = 0;
  }
  bool ans = true;
  for (int i = 0; i < N-1; i++) {
    if (H[i] > H[i+1]) {
      ans = false;
      break;
    }
  }
  cout << (ans ? "Yes" : "No") << endl;
}

Measured memory_bytes: 1024
n = int(input())
a = list(map(int, input().split()))
b = [0] * (pow(10,5) + 1)
for i in range(n):
  if a[i] == 0:
    b[0] += 1
    b[1] += 1
  elif a[i] == pow(10,5):
    b[pow(10,5) - 1] += 1
    b[pow(10,5)] += 1
  else:
    b[a[i]] += 1
    b[a[i] - 1] += 1
    b[a[i] + 1] += 1
print(max(b))

Measured memory_bytes: 13964
from sys import stdin 
a = map(int,stdin.readline().split())
ans = 0 
while True:
    b = set(a)
    if len(b)==1:
        break 
    a.sort()
    c = []
    if a[0]==a[1]:
        c = [a[0]+1,a[1]+1,a[2]]
    else:
        c = [a[0]+2,a[1],a[2]]
    ans+= 1 
    a = list(c)
print ans
        

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

using namespace std;

typedef long long ll;

const int maxn = 44;
const int masklen = 1<<17;
const ll mod = 1e9+7;

bool buf;
int n, x, y, z;
ll dp[maxn][masklen];
ll res = 1;

int main() {

	buf = scanf("%d%d%d%d", &n, &x, &y, &z);

	int bad = (1<<(z-1)) | (1<<(y+z-1)) | (1<<(x+y+z-1));

	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 10; j++) {
			for (int mask = 0; mask < masklen; mask++) {
				int nxt = ((mask << j) + (1 << (j-1))) % masklen;

				if ((bad&nxt) != bad)
					dp[i][nxt] = (dp[i][nxt] + dp[i-1][mask]) % mod;
			}
		}
		res = (10ll * res) % mod;
	}

	for (int mask = 0; mask < masklen; mask++) {
		if ((bad&mask) != bad)
			res = (res - dp[n][mask] + mod) % mod;
	}

	printf("%lld\n", res);

	return 0;
}

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

int main(){
  const int denomi = 1000000000+7;
  long int power=1;
  //整数入力
  int n;
  cin >> n;
  
  while(n>denomi){
    n-=denomi;
  }
  
  //大きい順にかけないとオーバーフロー起こす可能性あり?
  for(int i=n; i>=1; i--){
    while(power>denomi){
      power-=denomi;
    }
    power*=i;
  }
  
  cout << power << endl;
  
  return 0;
}

Measured memory_bytes: 256
"""
DFS
"""
# 再帰回数の上限を解除
import sys
sys.setrecursionlimit(10**7)


class Edge:
    def __init__(self, _to, _id):
        self.to = _to
        self.id = _id


def dfs(vertex, parent_color=-1, parent_vertex=-1):
    color = 1
    for g in graph[vertex]:
        u = g.to
        ei = g.id
        if u == parent_vertex:
            continue
        if color == parent_color:
            color += 1
        ans[ei] = color
        color += 1
        dfs(u, ans[ei], vertex)


N = int(input())
graph = [[] for _ in range(N)]
ans = [0 for _ in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(Edge(b, i))
    graph[b].append(Edge(a, i))

dfs(0)

# 最大次数が色数となる
mx = max([len(g) for g in graph])
print(mx)

for i in range(N-1):
    print(ans[i])



Measured memory_bytes: 105628
#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
int n,x,a[maxn];
int main(){
    scanf("%d%d",&n,&x);
    for(register int i=0;i<n;i++) scanf("%d",&a[i]);
    sort(a,a+n);
    for(register int i=0;i<n;i++){
        x-=a[i];
        if(!x){printf("%d",i+1);return 0;}
        else if(x<0){printf("%d",i);return 0;}
    }
    printf("%d",n-1);
    return 0;
}

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

int main() {
	string s;
	cin>>s;
	int x=0;
	for(int i=0;i<3;i++){
		if(s[i]=='R'){
			x+=1;
		}
	}
	if(x==2 && s=="RSR"){
		x=1;
	}
	cout<<x;
	return 0;
}

Measured memory_bytes: 3624
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int CM = 1 << 17, CL = 12;
char cn[CM + CL], * ci = cn + CM + CL, * owa = cn + CM, ct;
const ll ma0 = 1157442765409226768;
const ll ma1 = 1085102592571150095;
const ll ma2 = 71777214294589695;
const ll ma3 = 281470681808895;
const ll ma4 = 4294967295;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	ll tmp = *(ll*)ci;
	int dig = 68 - __builtin_ctzll((tmp & ma0) ^ ma0);
	tmp = tmp << dig & ma1;
	tmp = tmp * 10 + (tmp >> 8) & ma2;
	tmp = tmp * 100 + (tmp >> 16) & ma3;
	tmp = tmp * 10000 + (tmp >> 32) & ma4;
	ci += 72 - dig >> 3;
	return tmp;
}

char A[1000001];

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


	int N = getint();

	rep(i, N) A[getint()]++;

	if (A[1]) {
		if (A[1] == 1) co(1);
		else co(0);
		return 0;
	}
	if (A[2]) {
		int kotae = (A[2] == 1);
		for (int i = 3; i <= 500000; i += 2) {
			if (A[i]) {
				kotae += (A[i] == 1);
				for (int j = i + i; j <= 1000000; j += i) {
					A[j] = 0;
				}
			}
		}
		for (int i = 500001; i <= 1000000; i += 2) kotae += (A[i] == 1);
		co(kotae);
		return 0;
	}

	int kotae = 0;
	for (int i = 2; i <= 500000; i++) {
		if (A[i]) {
			kotae += (A[i] == 1);
			for (int j = i + i; j <= 1000000; j += i) {
				A[j] = 0;
			}
		}
	}
	for (int i = 500001; i <= 1000000; i++) kotae += (A[i] == 1);
	co(kotae);

	Would you please return 0;
}

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

class MainClass
{
    static void Main()
    {
        var N = long.Parse(ReadLine());
        var list = new List<long>();
        
        var n = N;
        for (int i = 1; i < Sqrt(N)+1; i++)
        {
            if (N % i == 0) list.Add(i);
        }
        var A = list.Last();
        WriteLine(Max(A.ToString().Length,(N/A).ToString().Length));
    }
}


Measured memory_bytes: 28140
#include<iostream>
#include <algorithm>

using namespace std; 

int max_array(int n[],int len)
{
  int i,tmp;
  tmp = n[0];
  for (int i=1; i<len; i++) {
    if (tmp < n[i]){
      tmp = n[i];
    }
  }
  return tmp;
}

int min_array(int n[],int len)
{
  int i,tmp;
  tmp = n[0];
  for (int i=1; i<len; i++) {
    if (tmp > n[i]){
      tmp = n[i];
    }
  }
  return tmp;
}

int main (void) {

  int N;
  int a[110];
  int i;

  cin >> N;
  for (i=0; i<N; i++){
    cin >> a[i];
  }
  
  int max, min;
  max = max_array(a, N);
  min = min_array(a, N);

  cout << max - min << endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){

    int n;
    cin>>n;

    int arr[n];

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

    int mn = arr[0];

    int cnt = 1;

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

        if(arr[i]<mn){
            cnt++;
        }
        mn = min(arr[i],mn);
    }

    cout<<cnt<<endl;

}


Measured memory_bytes: 1024
#include<iostream>
#include<bits/stdc++.h>
#include<iomanip>
#include<math.h>
#include<vector>
#include<cctype>
#include<string>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
std::string line;


int main(){

   int n;
   int a[110];
   cin >> n;
   rep(i,n) cin >> a[i];

   sort(a,a+n, greater<int>());

int alice = 0;
int bob = 0;
   rep(i,n){
       if(i%2==0) alice += a[i];
       else bob += a[i];
   }

   cout << alice - bob << endl;


   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
const int N = 1e5 + 5;
#define int long long int
 
int32_t main() {
    IOS ;
    int n, w ; cin >> n >> w ; 
    int wt[n+1], val[n+1], dp[n+1][w+1] ; 
    for(int i=1; i<n+1; i++) cin >> wt[i] >> val[i] ; 
 
    for(int i=0; i<n+1; i++) 
    for(int j=0; j<w+1; j++) 
    if(i == 0 or j == 0) dp[i][j] = 0 ; 
    else {
        int x = dp[i-1][j] ; 
        int y = ((j - wt[i]) >= 0) ? val[i] + dp[i-1][j - wt[i]] : 0 ;
        dp[i][j] = max(x, y) ;
    } 

    cout << dp[n][w] ;
    return 0 ;
}

Measured memory_bytes: 82496
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<int>>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

int main() {
    int H, W;
    cin >> H >> W;
    ll ans = LLINF;
    for(int h = 1; h < H; ++h) {
        ll s1 = (ll)h * W, s2 = (ll)(H - h) * (W / 2),
           s3 = (ll)(H - h) * W - s2;
        ll mi = min(s1, min(s2, s3)), ma = max(s1, max(s2, s3));
        ans = min(ans, ma - mi);
        s2 = (ll)(H - h) / 2 * W, s3 = (ll)(H - h) * W - s2;
        mi = min(s1, min(s2, s3)), ma = max(s1, max(s2, s3));
        ans = min(ans, ma - mi);
    }
    for(int w = 1; w < W; ++w) {
        ll s1 = (ll)w * H, s2 = (ll)(W - w) * (H / 2),
           s3 = (ll)(W - w) * H - s2;
        ll mi = min(s1, min(s2, s3)), ma = max(s1, max(s2, s3));
        ans = min(ans, ma - mi);
        s2 = (ll)(W - w) / 2 * H, s3 = (ll)(W - w) * H - s2;
        mi = min(s1, min(s2, s3)), ma = max(s1, max(s2, s3));
        ans = min(ans, ma - mi);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;
using lli = long long int;
int mem[30][200005]= {};
int main() {
    int n;cin >> n;
    vector<int> a(n);
    rep(i,n)cin >> a[i];
    rep(i,n){
        rep(j,30){
            if(1 & (a[i] >> j)){
                mem[j][i+1] = mem[j][i] + 1;
            }else {
                mem[j][i+1] = mem[j][i];
            }
        }
    }
    lli ans = 0;
    rep(i,n){
        int up = i+1;
        int low = 0;
        while(up-low>1){
            int mid = (up+low)>>1;
            bool flag = true;
            rep(j,30){
                if( mem[j][i+1] - mem[j][mid-1] > 1){
                    flag  = false;
                }
            }
            if(flag){
                up = mid;
            }else {
                low = mid;
            }
        }
        // cerr << i<< " " << up << " " << low << " " << i - low + 1 << endl;
         ans += i - low + 1   ;
    }
    cout << ans << endl;
}


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

int main(void) {
    int H, W, K, N, A[30], B[30], C[30], D[30], x, m, b, i, j, k, bit;
    char S[15][1005];
    scanf("%d%d%d", &H, &W, &K);
    for (i=0; i<H; i++) scanf("%s", S[i]);
    m=10000;
    for (bit=0; bit<(1<<(H-1)); bit++) {
        vector<int> s;
        for (i=0; i<H-1; i++) {
            if (bit & (1<<i)) s.push_back(i);
        }
        
        N=(int)s.size();
        // printf("%d: ", bit);
        // for (i=0; i<(int)s.size(); i++) printf("%d ", s[i]);
        
        for (i=0; i<N+1; i++) A[i]=0;
        for (i=0; i<H; i++) B[i]=0;
        for (i=0; i<N; i++) B[s[i]+1]=1;
        C[0]=0;
        for (i=1; i<H; i++) C[i]=C[i-1]+(B[i]?1:0);
        for (i=0; i<N+1; i++) D[i]=0;
        // printf("| ");
        // for (i=0; i<H; i++) printf("%d ", C[i]);
        
        // printf("\n");
        
        
        b=1;
        x=N;
        for (i=0; i<W; i++) {
            // printf("[]\n");
            for (j=0; j<N+1; j++) D[j]=0;
            for (j=0; j<H; j++) {
                if (S[j][i]=='1') D[C[j]]++;
                if (D[C[j]]>K) {
                    b=0;
                    break;
                }
            }
            for (j=0; j<N+1; j++) A[j]+=D[j];
            for (j=0; j<N+1; j++) {
                if (A[j]>K) {
                    x++;
                    for (k=0; k<N+1; k++) A[k]=0;
                    for (k=0; k<N+1; k++) A[k]=0;
                    for (k=0; k<H; k++) {
                        if (S[k][i]=='1') A[C[k]]++;
                        if (A[C[k]]>K) {
                            b=0;
                            break;
                        }
                    }
                }
            }
        }
        if (x<m && b==1) m=x;
        
        // printf("[%d]", x);
        // printf("\n");
    }
    printf("%d", m);
    return 0;
}

Measured memory_bytes: 256
s = str(input())
q = int(input())
Q = [list(input().split()) for i in range(q)]
head = ''
bottom = ''
reverse = False
for i in range(q):
    if Q[i][0] == '1':
        reverse = not reverse
    else: #Ti == 2
        if Q[i][1] == '1':
            if reverse == False:
                head = Q[i][2] + head
            else:
                bottom = bottom + Q[i][2]
        if Q[i][1] == '2':
            if reverse == False:
                bottom = bottom + Q[i][2]
            else:
                head = Q[i][2] + head
s = head + s + bottom
ans = ''
if reverse == True:
    for i in range(len(s)):
        ans += s[-1 * (i + 1)]
else:
    ans = s
print(ans)

Measured memory_bytes: 32168
import java.util.Scanner;
class Main {
  public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
for(;;) {
	int m=sc.nextInt();
	int f=sc.nextInt();
	int r=sc.nextInt();
	if(m==-1&&f==-1&&r==-1)break;
	if(m==-1||f==-1) {
		System.out.println("F");
	}
	else if(m+f>=80) {
		System.out.println("A");
	}
	else if(65<=m+f&&m+f<80) {
		System.out.println("B");
	}
	else if(50<=m+f&&m+f<65) {
		System.out.println("C");
	}
	else if(30<=m+f&&m+f<50) {
		if(r>=50) {
		System.out.println("C");
		}
		else {
			System.out.println("D");
		}
	}
	else {
		System.out.println("F");
	}
}
sc.close();
  }
}



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

using namespace std;

typedef pair<int, int> P;

#define INF 1000000000

struct Edge {
	int to, cap, cost, rev;
};

vector< vector<Edge> > G;

int dist[4000], h[4000] = {0}, prevV[4000], prevE[4000];
int flow(int s, int t, int f) {
	int res = 0;
	while (f > 0) {
		fill(&dist[0], &dist[0]+4000, INF); dist[s] = 0;
		priority_queue<P, vector<P>, greater<P> > Q; Q.push({0, s});
		while ( !Q.empty() ) {
			P p = Q.top(); Q.pop();
			int v = p.second;
			if (dist[v] < p.first) continue;
			for (int i = 0; i < G[v].size(); ++i) {
				Edge& e = G[v][i];
				if (e.cap > 0 && dist[v]+e.cost+h[v]-h[e.to] < dist[e.to]) {
					dist[e.to] = dist[v]+e.cost+h[v]-h[e.to];
					prevV[e.to] = v;
					prevE[e.to] = i;
					Q.push({dist[e.to], e.to});
				}
			}
		}
		if (dist[t] == INF) {
			cout << "ERROR: f=" << f << endl;
			exit(1);
		}
		for (int i = 0; i < G.size(); ++i) h[i] += dist[i];

		int d = f;
		for (int v = t; v != s; v = prevV[v]) {
			d = min(d, G[prevV[v]][prevE[v]].cap);
		}
		f -= d;
		res += d * h[t];
		for (int v = t; v != s; v = prevV[v]) {
			Edge& e = G[prevV[v]][prevE[v]];
			e.cap -= d;
			G[e.to][e.rev].cap += d;
		}
	}
	return res;
}
void addEdge(int from, int to, int cap, int cost) {
	G[from].push_back({to, cap, cost, (int)G[to].size()});
	G[to].push_back({from, 0, -cost, (int)G[from].size()-1});
}

int main() {
	int N; cin >> N;
	vector<int> A(N), B(N);
	for (int i = 0; i < N; ++i) {
		cin >> A[i] >> B[i];
	}
	map<int, int> m; int msz = 0;
	for (int i = 0; i < N; ++i) {
		if (m.find(A[i]) == m.end()) {
			m[A[i]] = msz++;
		}
	}
	for (int i = 0; i < N; ++i) {
		if (m.find(B[i]) == m.end()) {
			m[B[i]] = msz++;
		}
	}

	int s = msz+N, t = s+1;
	G.resize(t+1);

	for (int i = 0; i < N; ++i) {
		addEdge(m[A[i]], msz+i, 1, -B[i]);
		addEdge(m[B[i]], msz+i, 1, -A[i]);
		addEdge(msz+i, t, 1, 0);
	}
	for (int i = 0; i < msz; ++i) {
		addEdge(s, i, 1, 0);
		addEdge(i, t, 1, 0);
	}

	cout << -flow(s, t, msz) << endl;
}

Measured memory_bytes: 1780
#include<bits/stdc++.h>
using namespace std;
#define LL long long int
#define DL double
#define MLL map<LL,LL>::iterator
#define MSL map<string,LL>::iterator
#define MLS map<LL,string>::iterator
#define MSS map<string,string>::iterator
#define MCL map<char,LL>::iterator
#define SL set<LL>::iterator
#define SS set<string>::iterator
#define VL vector<LL>::iterator
#define G getline
#define SZ size()
#define IN insert
#define C clear()
#define B begin()
#define F front()
#define T top()
#define E end()
#define EM empty()
#define V vector
#define Q queue
#define DQ deque
#define PQ priority_queue
#define ST stack
#define FI first
#define SE second
#define PI acos(-1)
#define PS push
#define PP pop()
#define PSF push_front
#define PSB push_back
#define PPF pop_front()
#define PPB pop_back()
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
LL v[3];
int main()
{
    FAST;
    LL n,m,i,j,k,p,q,o,l,s,t,z;
    cin>>n>>m>>o>>p>>q;
    k=0;
    if(n+m>o*2)
    {
        z=min(p,q);
        k+=(z*o*2);
        if(p>q)
        {
            l=p-q;
            if(l*n<=l*o*2)
            {
                k+=(l*n);
            }
            else
            {
                k+=(l*o*2);

            }
        }
        else
        {
            l=q-p;
            if(l*m<=l*o*2)
            {
                k+=(l*m);
            }
            else
            {
                k+=(l*o*2);

            }
        }

    }
    else
    {
        k+=(p*n);
        k+=(q*m);
    }
    cout<<k<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=998244353;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

#include<atcoder/dsu>
using namespace atcoder;

int n,q;

int main(){
	cin>>n>>q;
	dsu uft(n);
	for(int i=0;i<q;i++){
		int t,u,v;
		cin>>t>>u>>v;
		if(t==0) uft.merge(u,v);
		else cout<<uft.same(u,v)<<endl;
	}
}

Measured memory_bytes: 3792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf =1e18;
const int maxn=1e5+7;
typedef long long ll;
int T;
int a,b,c,n;
ll la[maxn],lb[maxn],x,ans;
double pi=3.14159265359;
double d,r;
int main()
{
   scanf("%d%d%d",&a,&b,&c);

   for(int i=0;i<a;i++)
     scanf("%lld",&la[i]);
   for(int i=0;i<b;i++)
     scanf("%lld",&lb[i]);
   while(c--)
   {
       scanf("%lld",&x);
       ans=inf;
       int aa=lower_bound(la,la+a,x)-la;


       int bb=lower_bound(lb,lb+b,x)-lb;

       //cout<<bL<<"   "<<bR<<endl;
       if(aa<a&&bb<b)
          ans=min(ans,max(la[aa],lb[bb])-x);
       if(aa&&bb)
           ans=min(ans,x-min(la[aa-1],lb[bb-1]));
       if(aa&&bb<b)
           ans=min(ans,lb[bb]-la[aa-1]+min(x-la[aa-1],lb[bb]-x));
       if(aa<a&&bb)
           ans=min(ans,la[aa]-lb[bb-1]+min(x-lb[bb-1],la[aa]-x));
       printf("%lld\n",ans);
   }
}


Measured memory_bytes: 2816
n, k = map(int, input().split())
l = [int(input()) for _ in range(n)]
l = sorted(l)
#print(l)
x = []
for i in range(n-k+1):
    x.append(l[i+k-1] - l[i])
x  = sorted(x)
#print(x)

print(min(x[:k-1]))


Measured memory_bytes: 12040
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Map;
import java.util.Scanner;
import java.util.HashMap;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        D solver = new D();
        solver.solve(1, in, out);
        out.close();
    }

    static class D {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            int n = Integer.parseInt(in.next());
            Long a[] = new Long[n];
            for (int i = 0; i < n; i++) {
                a[i] = Long.parseLong(in.next());
            }

            Map<Long, Long> ma = new HashMap<>();

            for (int i = 0; i < n; i++) {
                if (ma.containsKey(a[i])) {
                    Long tmp = ma.get(a[i]);
                    tmp++;
                    ma.put(a[i], tmp);
                } else {
                    ma.put(a[i], 1L);
                }
            }

            Long res = 0L;
            for (Long key : ma.keySet()) {
                res += ma.get(key) * (ma.get(key) - 1) / 2;
            }

            for (int i = 0; i < n; i++) {
                Long val = ma.get(a[i]);
                Long bef = val * (val - 1) / 2;
                Long aft = (val - 1) * (val - 2) / 2;
                out.println(res + aft - bef);
            }

        }

    }
}



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

int main(){
int A, B, C, X;
  cin >> A >> B >> C >> X;
int cnt = 0;
  for(int i = 0;i <= A;i++){
    for(int j = 0;j <= B;j++){
      for(int k = 0;k <= C;k++){
        if(X == i * 500 + j * 100 + k * 50){
        cnt++;
        }
      }
    }
  }
  
  cout << cnt << endl;
  
  return 0;
}

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

int main(){
    vector <int> a(3);
    cin >> a[0] >> a[1] >>a[2];
    sort(a.begin(),a.end());
    if(a[0] == 5 && a[1] == 5 && a[2] == 7){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.nio.CharBuffer;
import java.util.NoSuchElementException;

public class Main {

    public static void main(String[] args) {
        SimpleScanner scanner = new SimpleScanner(System.in);
        PrintWriter writer = new PrintWriter(System.out);

        long n = scanner.nextLong();
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        if (a % 2 == b % 2)
            writer.println((b - a) / 2);
        else
            writer.println(Math.min(a + (b - a - 1) / 2, (n - b + 1) + (b - a - 1) / 2));
        writer.close();
    }

    private static class SimpleScanner {

        private static final int BUFFER_SIZE = 10240;

        private Readable in;
        private CharBuffer buffer;
        private boolean eof;

        SimpleScanner(InputStream in) {
            this.in = new BufferedReader(new InputStreamReader(in));
            buffer = CharBuffer.allocate(BUFFER_SIZE);
            buffer.limit(0);
            eof = false;
        }


        private char read() {
            if (!buffer.hasRemaining()) {
                buffer.clear();
                int n;
                try {
                    n = in.read(buffer);
                } catch (IOException e) {
                    n = -1;
                }
                if (n <= 0) {
                    eof = true;
                    return '\0';
                }
                buffer.flip();
            }
            return buffer.get();
        }

        private void checkEof() {
            if (eof)
                throw new NoSuchElementException();
        }

        private char nextChar() {
            checkEof();
            char b = read();
            checkEof();
            return b;
        }

        private String next() {
            char b;
            do {
                b = read();
                checkEof();
            } while (Character.isWhitespace(b));
            StringBuilder sb = new StringBuilder();
            do {
                sb.append(b);
                b = read();
            } while (!eof && !Character.isWhitespace(b));
            return sb.toString();
        }

        private int nextInt() {
            return Integer.parseInt(next());
        }

        private long nextLong() {
            return Long.parseLong(next());
        }

        private double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}

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

using namespace std;

const int N = 5e5 + 5;

int a[N], p[N], s[N];

signed main(){
	#ifdef LOCAL
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int a,b;
	cin>>a>>b;
	if(a%b)cout<<a/b+1;
	else cout<<a/b;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define pb push_back
#define mp make_pair
#define F .first
#define S .second 
using ll=long long;
using ld=long double;
const ll INF = 1LL<<60;
const ll mod=1e9+7;
using namespace std;
ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }

long long modpow(ll a, ll b, ll mod) {
    ll res=1;
    while (b) {
        if (b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}


ll dp[220000];
map<ll,ll> p;
int main(){
    ll ans=0;
    string s;
    cin>>s;
    long sl=s.length();
    char t=s[sl-1];
    dp[0]=(t-'0')%2019;
    rep(i,1,sl){
        ll y=s[sl-i-1]-'0';
        ll z=y*modpow(10,i,2019);
        dp[i]=(dp[i-1]+z)%2019;
    }
    rep(i,0,sl)p[dp[i]]++;  
    for(map<ll,ll>::iterator it=p.begin();it!=p.end();it++){
    ll ff=it->second;
    ans+=ff*(ff-1)/2;
    if(it->first==0)ans+=ff;
    }
    cout<<ans;
}


Measured memory_bytes: 5276
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main{
  public static void main(String args[]) throws IOException{
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


   String st = br.readLine();

   int n = Integer.parseInt( st );
   double[] abs = new double[n];
   String[] x = br.readLine().split(" ");
   String[] y = br.readLine().split(" ");

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

	   abs[i] = Math.abs( Double.parseDouble(x[i]) - Double.parseDouble(y[i]) );//???????????????????????¢
	   p1 += abs[i];

   }
   System.out.println(p1);

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

	   sum += Math.pow(Math.abs( Double.parseDouble(x[i]) - Double.parseDouble(y[i]) ) , 2);//???????????????????????¢

   }
   double p2 = Math.sqrt(sum);
   System.out.println(p2);

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

	   sum2 += Math.pow(Math.abs( Double.parseDouble(x[i]) - Double.parseDouble(y[i]) ) , 3);//n=3??????????????????????????¢

   }

  
   double p3 = Math.pow(sum2 , 1.0 / 3.0);
   System.out.println(p3);


   double Ch = abs[0];
   for(int j = 0 ;j < n; j++){
     if(Ch < abs[j]){
       Ch = abs[j];//?????§????????§????????¢
     }
   }
   System.out.println(Ch);

  }
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

int main() {
    //cout.precision(10);
    int N;
    cin >> N;
    ll left = 1;
    ll right = 1;
    while(N--) {
        ll t, a;
        cin >> t >> a;
        ll product = (left + t - 1) / t;
        product = max(product, (right + a - 1) / a);
        left = t * product;
        right = a * product;
    }
    cout << left + right << endl;
    return 0;
}


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

int main()
{
    int n;
    vector<int> v;

    while( cin >> n )
    {
        if( n == 1 )
            break;

        cout << n << ":";
        for( int i = 7; i < 300000; i += 7 )
        {
            if( n % ( i - 1 ) == 0 )
            {
                bool judge = true;
                for( int j = 0; j < v.size(); j++ )
                    if( ( i - 1 ) % v[j] == 0 )
                    {
                        judge = false;
                        break;
                    }
                if( judge )
                    v.push_back(i-1);
            }
            if( n % ( i + 1 ) == 0 )
            {
                bool judge = true;
                for( int j = 0; j < v.size(); j++ )
                    if( ( i + 1 ) % v[j] == 0 )
                    {
                        judge = false;
                        break;
                    }
                if( judge )
                    v.push_back(i+1);
            }
        }
        for( int i = 0; i < v.size(); i++ )
            cout << " " << v[i];
        cout << endl;
        v.clear();
    }
    return 0;
}


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

#define MAX 362880
#define N 3
#define N2 9


typedef struct puzzle{
  int f[N2];
  int space;
  int path;
}PUZZLE;

static const int dx[4] = {-1, 0, 1, 0};
static const int dy[4] = {0, -1, 0, 1};

int V[MAX];

PUZZLE Q[MAX];
int head, tail;

void push(PUZZLE x){
  Q[tail] = x;
  tail = (tail+1)%MAX;
}

PUZZLE pop(){
  PUZZLE x;
  x = Q[head];
  head = (head+1)%MAX;
  return x;
}

int check(PUZZLE p){
  int i, j, fac, count, res = 0;
  for(i = 0, fac = 1; i < N2; fac*= ++i){
    for(j = 0, count = 0; j < i; j++){
      if(p.f[j] < p.f[i]) count++;
    }
    res += count*fac;
  }
  return res;
}

int isTarget(PUZZLE p){
  int i;
  for(i = 0; i < N2; i++ )
    if(p.f[i] != (i + 1) )
      return 0;
  return 1;
}

int bfs(PUZZLE s){
  int sx, sy, tx, ty, r, temp;
  PUZZLE u, v;

  s.path = 0;
  push(s);
  V[check(s)] = 1;

  while(head != tail){
    u = pop();

    if( isTarget(u))
      return u.path;

    sx = u.space / N;
    sy = u.space % N;

    for ( r = 0; r < 4; r++ ) {
      tx = sx + dx[r];
      ty = sy + dy[r];

      if(tx < 0 || ty < 0 || tx >= N || ty >= N)
	continue;
      
      v = u;
      temp = v.f[u.space];
      v.f[u.space] = v.f[tx * N + ty];
      v.f[tx * N + ty] = temp;

      v.space = tx * N + ty;

      if( !V[check(v)] ){
	V[check(v)] = 1;
	v.path++;
	push(v);
      }
    }
  }
  return -1;
}

int main(){
  int i, ans;
  PUZZLE in;

  for( i = 0; i < N2; i++ ) {
    scanf(" %d", &in.f[i]);
    if( in.f[i] == 0) {
      in.f[i] = N2;
      in.space = i;
    }
  }

  ans = bfs(in);
  printf("%d\n", ans);

  return 0;
}





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

#define ll long long
#define ar array

string s, t;

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

	cin >> s >> t;
	int ans=0;
	for (int i=0; i<s.size(); ++i)
		ans+=s[i]!=t[i];
	cout << ans << '\n';

	return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/


Measured memory_bytes: 3780
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[[-1 for _ in range(W+1)] for _ in range(N+1)]
for i in range(W+1):
    dp[N][i] = 0
for i in range(0,N)[::-1]:
    for j in range(W+1):
        if j < w[i]:
            dp[i][j]=dp[i+1][j]
        else:
            dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
print(dp[0][-1])

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

int main() {
    int N;
    cin >> N;
    vector<vector<int>> cand(3,vector<int>(110));
    vector<int> asum(110);
    vector<int> a2sum(110);
    int buf;

    for(int i=0;i<2;i++){
        for(int j=0;j<N;j++){
            cin >> cand[i][j];

            if(j==0) buf=0;
            else if(i==0)buf=asum[j-1];
            else if(i==1)buf=a2sum[j-1];

            if(i==0) asum[j]=cand[i][j]+buf;
            else a2sum[j]=cand[i][j]+buf;
        }
    }
    int x=0,y=0;
    int ans=0;
    for(int i=0;i<N;i++){
        if(i==0) buf=0;
        else buf=a2sum[i-1];
        ans=max(ans,asum[i]+a2sum[N-1]-buf);
    }
    cout << ans << endl;
}

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

int main() {
	int n,i,x=0;
	cin>>n;
	string s;
	cin>>s;
	for(i=0;i<n-2;i++)
	{
		if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C') x++;
	}
	cout<<x;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000000;
constexpr ll INF= 9 * 1e18;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<ll,ll> P;

template<typename T>
T Pow(T a,T b) {
    T ret = 1;
    for(int i = 0;i < b;i++) {
        ret *= a;
    }
    return ret;
}

ll mod(ll val) {
    ll res = val % MOD;
    if(res < 0) {
        res += MOD;
    }
    return res;
}

int main() {
    string S,T;
    cin >> S >> T;
    sort(S.begin(),S.end());
    sort(T.begin(),T.end());
    reverse(T.begin(),T.end());
    if(T > S) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
import bisect
n = int(input())
dat = list(map(int, input().split()))
dat.sort(reverse=True)
dat = list(map(lambda x: -x, dat))
#print(dat)
res = 0
for a in range(n):
    #print("a={0}, [{1}]".format(dat[a],a))
    for b in range(a+1, n):
        #print("b={0}, [{1}]".format(dat[b],b))
        cind = bisect.bisect_left(dat, dat[a] - dat[b], b)
        cannum = cind - (b+1)
        cannum = 0 if cannum < 0 else cannum
        #print("cind", cind)
        #print("cannum", cannum)
        res += cannum
print(res)

Measured memory_bytes: 3316
n=int(input())
a=list(map(int,input().split()))

dp=[0]*(n)
dp[0]=0
dp[1]=abs(a[1]-a[0])

for i in range (2,n):
  dp[i]=min(dp[i-2]+abs(a[i]-a[i-2]),dp[i-1]+abs(a[i]-a[i-1]))
  #print(dp)
  
print(dp[n-1])

Measured memory_bytes: 84724
/* 
	Author: ankrypt
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int
#define ff first
#define ss second
#define all(x) x.begin(), x.end() 
#define ub upper_bound
#define lb lower_bound
#define MAX_INT 15
#define fi(a, b, c, d) for(int a = b; a < c; a += d)
#define fl(a, b, c, d) for(ll a = b; a < c; a += d)
#define fei(a, b, c, d) for(int a = b; a <= c; a += d)
#define fel(a, b, c, d) for(ll a = b; a <= c; a += d)
#define quit exit(0)
#define pi 3.141592653589793238

ll N, M, A, B, C;
ll arr[MAX_INT], arr1[MAX_INT], data[MAX_INT];
vector<ll> V;


int main() {
	scanf("%lld", &N);
	double ans = 2 * pi * N;
	printf("%0.12lf\n", ans);	
	return 0;
}
/*
	Powered by Buggy Plugin
*/




Measured memory_bytes: 3812
import java.util.ArrayDeque;
import java.util.Scanner;

class A {
    static final int[] di = {-1, 0, 1, 0};
    static final int[] dj = {0, -1, 0, 1};

    public static void main(String... args) {
        final Scanner sc = new Scanner(System.in);
        final int H = sc.nextInt();
        final int W = sc.nextInt();
        final char[][] map = new char[H][];
        for (int i = 0; i < H; i++)
            map[i] = sc.next().toCharArray();
        final int[][] dist = new int[H][W];
        final ArrayDeque<Integer> que = new ArrayDeque<>();
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                if (map[i][j] == '#')
                    que.offer(i * W + j);
                else
                    dist[i][j] = Integer.MAX_VALUE;
        while (!que.isEmpty()) {
            final int p = que.poll();
            final int i = p / W;
            final int j = p % W;
            for (int d = 0; d < 4; d++) {
                final int ni = i + di[d];
                final int nj = j + dj[d];
                if (0 <= ni && ni < H && 0 <= nj && nj < W && dist[ni][nj] == Integer.MAX_VALUE) {
                    dist[ni][nj] = dist[i][j] + 1;
                    que.offer(ni * W + nj);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                ans = Math.max(ans, dist[i][j]);
        System.out.println(ans);
    }
}

public class Main {
    public static void main(String...args) {
        A.main();
    }
}


Measured memory_bytes: 65644
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp make_pair
#define elif else if
#define prev prev2
#define Edge pair <int, int>
#define next next2
#define u first
#define v second
#define int long long
typedef long long ll;
typedef long double ld;
const int MAXN = 1007, N = 1007, MAXM = 2e5 + 7;
vector<int> g[MAXM], gt[MAXM];
int a[MAXM], b[MAXM], c1[MAXM], c2[MAXM];
vector<int> topsort;
int vis[MAXM];
Edge ed[MAXM];
bool used[MAXM];
void dfs(int u) {
    used[u] = 1;
    for (int e : g[u]) {
        int v = ed[e].u ^ ed[e].v ^ u;
        if (!used[v]) dfs(v);
    }   
}   
void solve(int u) {
    memset(used, 0, sizeof used);
    used[u] = 1;
    for (int e : g[u]) {
        int v = ed[e].u ^ ed[e].v ^ u;
        if (used[v]) {
            c2[e] = 1;
        }       
        else {
            dfs(v);
        }   
    }   
    memset(used, 0, sizeof used);
    used[u] = 1;
    reverse(g[u].begin(), g[u].end());
    for (int e : g[u]) {
        int v = ed[e].u ^ ed[e].v ^ u;
        if (used[v]) {
            c2[e] = 1;
        }       
        else {
            dfs(v);
        }   
    }   
}   
void dfst1(int v) {
    vis[v] = 1;
    for (int e : g[v]) {
        int u = b[e];
        if (!vis[u])
            dfst1(u);
    }
    topsort.push_back(v);
}
int clr = 0;
void dfst2(int v) {
    vis[v] = clr;
    for (int e : gt[v]) {
        int u = a[e];
        if (!vis[u])
            dfst2(u);
    }
}
void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> a[i] >> b[i];
        --a[i];
        --b[i];
        g[a[i]].push_back(i);
        gt[b[i]].push_back(i);
    }
    for (int i = 0; i < n; ++i)
        if (!vis[i])
            dfst1(i);
    fill(vis, vis + n, 0);
    reverse(topsort.begin(), topsort.end());
    for (int v : topsort)
        if (!vis[v]) {
            ++clr;
            dfst2(v);
        }

    for (int i = 0; i < m; ++i) 
        c1[i] = (vis[a[i]] == vis[b[i]]);
    for (int i = 0; i < m; ++i) {
        ed[i] = {a[i], b[i]};
    }   
    for (int i = 0; i < n; ++i) {
        solve(i);
    }

    #ifdef HOME
    for (int i = 0; i < m; ++i) cout << c1[i] << ' '; cout << '\n';
    for (int i = 0; i < m; ++i) cout << c2[i] << ' '; cout << '\n';
    #endif

    for (int i = 0; i < m; ++i) {
        //cout << c1[i] << c2[i];
        if (c1[i] ^ c2[i]) {
            cout << "diff\n";
        }   
        else {
            cout << "same\n";
        }
    }   
    return;
}

signed main() {

    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #endif

    ios_base::sync_with_stdio(false);

    solve();

    return 0;
}

Measured memory_bytes: 27904
#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds; 

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define f first
#define s second
#define sz(x) ll(x.size())
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;++i)
#define fore(i,l,r) for(int i=int(l);i<=int(r);++i)
#define rep(i,begin,end) for(__typeof(end) i=(begin);i!=(end);i++)
#define fill(a,value) memset(a,value,sizeof(a));
#define gcd(a,b) __gcd((a),(b))
#define watch1(x) cout << (x) << endl
#define watch2(x,y) cout << (x) << " " << (y) << endl
#define watch3(x,y,z) cout << (x) << " " << (y) << " " << (z) << endl
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
 
typedef long long ll;
typedef long double ld; 
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
 
const ll mod = 1e9 + 7;
const int inf = 1e9 + 5;
const int N = 3e5 + 5;

ll a[N];

signed main(){
    fastio;
    ll i,j,n;
    cin>>n;
    for(i=1;i<=n;++i){
        cin>>a[i];
    }
    ll ans=0;
    for(j=0;j<62;++j){
        ll s=0,ns=0;
        for(i=1;i<=n;++i){
            if(a[i]&(1ll<<j))
                ++s;
            else
                ++ns;
        }
        ll p=(1ll<<j)%mod;
        p*=s;
        p%=mod;
        p*=ns;
        p%=mod;
        ans+=p;
        ans%=mod;
    }
    cout<<ans;
    return 0;
}

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

int main(){
	int N, K, x, A, B, mini=0;
	cin >> N >> K;

	for(int i=0; i<N; i++){
		cin >> x;
		A = x*2;
		B = (K-x) * 2;
		if( A < B ){
			mini += A;
		}
		else{
			mini += B;
		}
	}
	cout << mini << endl;
}


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

int main() {
	int n; cin>>n;
	vector<int> v(n),aux; 
	for(int i=0; i<n; i++){
		cin>>v[i];
	}
	aux = v;
	sort(aux.begin() , aux.end());
	
	int c = 0;
	for(int i=0; i<n && c<=2; i++){
		if(aux[i] != v[i]){
			c++;
		}
	}
	if(c<=2)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
int L,A,B,C,D;
int main(){
  scanf("%d %d %d %d %d",&L,&A,&B,&C,&D);
  int res=0;
  for(int i=0;i<L;i++){
    if(A<=0 && B<=0) res++;
    A-=C;
    B-=D;
  }
  printf("%d\n",res);
}

Measured memory_bytes: 1188
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;

#ifdef LOCAL
#include "../../dump.hpp"
#else
#define dump(...)
#endif

#define int ll
#define rep(i,n) for(int i=0,i##_cond=(n);i<i##_cond;++i)
#define FOR(i,a,b) for(int i=(a),i##_cond=(b);i<i##_cond;++i)
#define ROF(i,a,b) for(int i=(a)-1,i##_cond=(b);i>=i##_cond;--i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで大きい順
#define sz(x) ((int)(x).size())
#define pb push_back
#define fst first
#define snd second
#define mp make_pair
using ll  = long long;
using vi  = vector<int>;
using vvi = vector<vi>;
using vs  = vector<string>;
using pii = pair<int,int>;
// constexpr ll inf = 1ll<<61;
// constexpr ll mod = 1e9+7;
ll ext_gcd(ll a, ll b, ll &x, ll &y){ // ax+by=gcd(a,b)なるx,y,gcdを返す
  if(b == 0){
    x = 1; y = 0; return a;
  }
  ll q = a / b;
  ll g = ext_gcd(b, a-q*b, x, y);
  ll z = x - q * y;
  x = y; y = z;
  return g;
}

signed main(){
  int n; cin >> n;
  int a; cin >> a;
  rep(i,n-1){
    int b; cin >> b;
    int x,y;
    a = ext_gcd(a,b,x,y);
    dump(a);
  }
  cout << a << endl;
}

Measured memory_bytes: 384