akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main{
    final static long mod = 1000000007;
    //
    static ArrayList<intPair>[] list;
    static long[] distance;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        distance = new long[n];
        list = new ArrayList[n];
        for(int i = 0; i < n; i++){
          list[i] = new ArrayList<intPair>();
        }

        for(int i = 0; i < n - 1; i++){
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            int c = sc.nextInt();
            list[a].add(new intPair(b, c));
            list[b].add(new intPair(a, c));
        }
        int q = sc.nextInt();
        int k = sc.nextInt() - 1;
        dfs(k, -1);

        for(int i = 0; i < q; i++){
            System.out.println(distance[sc.nextInt() - 1] + distance[sc.nextInt() - 1]);
        }

    }
    public static void dfs(int current, int parent){
        for(intPair pair : list[current]){
            if(pair.getKey() != parent){
                distance[pair.getKey()] = distance[current] + pair.getValue();
                dfs(pair.getKey(), current);
            }
        }
    }
}

//
class intPair{
    int key;
    int value;
    public intPair(int key , int value){
        this.key = key;
        this.value = value;
    }
    int getKey(){
        return key;
    }
    int getValue(){
        return value;
    }
}

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		Boolean[][] is = new Boolean[4][13];
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 13; j++) {
				is[i][j] = false;
			}
		}
		int n = Integer.parseInt(str);
		for (int i = 0; i < n; i++) {
			str = br.readLine();
			String[] card = str.split(" ");
			if (card[0].equals("S")) {
				int k = Integer.parseInt(card[1]);
				is[0][k - 1] = true;
			} else if (card[0].equals("H")) {
				int k = Integer.parseInt(card[1]);
				is[1][k - 1] = true;
			} else if (card[0].equals("C")) {
				int k = Integer.parseInt(card[1]);
				is[2][k - 1] = true;
			} else {
				int k = Integer.parseInt(card[1]);
				is[3][k - 1] = true;
			}
		}
		String[] mark = { "S", "H", "C", "D" };
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 13; j++) {
				if (!is[i][j]) {
					System.out.println(mark[i] + " " + (j + 1));
				}
			}
		}
	}
}

Measured memory_bytes: 24500
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

ll memo[100010];

ll f(int n){
	if(memo[n] != -1) return memo[n];
	if(n <= 1) return 1LL;
	return memo[n] = n *f(n-1) % MOD;
}


int main(){
	int n;
	cin>>n;
	vi v(n);
	rep(i,n) cin>>v[i];
	rep(i, 100010) memo[i] = -1;
	memo[0] = 1LL;
	
	int ana = v[0] -1;
	int num = 1;

	ll ans = 1LL;

	for(int i = 1; i < n; i++){
		num++;
		ana += v[i]-v[i-1]-1;
		if(num >=ana+2){
			//(ans *= f(num))%=MOD;
			(ans *= num) %= MOD;
			num--;
			ana++;
		}
	}
	(ans *= f(num))%=MOD;
	cout<<ans<<endl;

}


Measured memory_bytes: 2944
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <deque>
#include <tuple>
#include <map>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main(){
  int n,a,b; cin>>n>>a>>b;
  cout << min(a,b) SP max((a+b)-n, 0) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
using namespace std;
typedef double  dbl;
typedef long long int lld;
#define foi(i,n) for(i = 0; i < n; i+=1)
#define fod(i,n) for(i=n-1; i >=0; i-=1)
#define MAX std::numeric_limits<lld>::max()
#define MIN std::numeric_limits<lld>::min()
#define FastIO  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main ()
{
      FastIO
      char a;
      cin >> a;
      cout << (++a);
      return 0;
}

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

public class Main {

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    char[] S = in.nextLine().toCharArray();
    Arrays.sort(S);
    if (S[0] == S[1] && S[1] != S[2] && S[2] == S[3]) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}


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

using namespace std;

int main() {
	int a, b; cin >> a >> b;

	if (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) {
		cout << "Possible" << endl;
	}
	else {
		cout << "Impossible" << endl;
	}
}

Measured memory_bytes: 256
#include <functional>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;

int main() {
    string s;
    cin >> s;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '?') {
            s[i] = 'D';
        }
    }

    cout << s << endl;
    return 0;
}

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

int main(){
  int n, m, i, j;
  int penalty[100000] = {0}, comp = 0;
  int ac[100000] = {0};
  char s[3]={'\0'};
  int penaltyTotal = 0;
  
  scanf("%d %d", &n,&m);
  for(i=0;i<n;i++){
    ac[i] = 0;
    penalty[i] = 0;
  }
  for(i=0;i<m;i++){
    scanf("%d %2s", &j, s);
    if(strcmp(s, "AC") == 0){
      if(ac[j-1] == 0) comp++;
      ac[j-1] = 1;
    }else{
      if(ac[j-1] == 0){
        penalty[j-1]++;
      }
    }
  }
  
  for(i=0;i<n;i++){
    if(ac[i] == 1) penaltyTotal += penalty[i];
  }

  printf("%d %d", comp, penaltyTotal);
  return 0;
}

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

int n;
int a[300][300];
bool memo[300][300];

int main() {
  IOS;
  cin >> n;
  REP(i,n) REP(j,n) cin >> a[i][j];

  REP(k,n) { // 経由する頂点
    REP(i,n) { // 開始頂点
      REP(j,n) { // 終端
        if (i == j || i == k || j == k) continue;
        int e1 = a[i][j];
        int e2 = a[i][k] + a[k][j];
        // 存在しない
        if (e1 > e2) { COUT(-1); return 0; }
        if (e1 == e2) memo[i][j] = true;
      }
    }
  }

  ll ans = 0;
  REP(i,n) REP(j,n) {
    if (!memo[i][j]) ans += a[i][j];
  }

  COUT(ans/2);
  return 0;
}

Measured memory_bytes: 3988
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    n, m, d = LI()

    # どの組も同じなので1組だけに着目
    if d == 0:
        ans = n * (m - 1) / n ** 2
    else:
        ans = 2 * (n - d) * (m - 1) / n ** 2

    print(ans)

if __name__ == '__main__':
    resolve()


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

using namespace std;
#define int long long
#define double long double
const double pi=3.14159265358979323846264L;
int n;
int x[200319],y[200319];
vector<pair<int,int> >coor;
int lis[200319],lisc=0;
#undef int
int main(){
	#define int long long
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int l,d,r,u;cin>>l>>d>>r>>u>>n;
	for(int i=0;i<n;i++){
		cin>>x[i]>>y[i];
	}
	if(l>r){
		l=100000000-l;r=100000000-r;
		for(int i=0;i<n;i++)x[i]=100000000-x[i];
	}
	if(d>u){
		d=100000000-d;u=100000000-u;
		for(int i=0;i<n;i++)y[i]=100000000-y[i];
	}
	for(int i=0;i<n;i++){
		if(x[i]<=r&&x[i]>=l&&y[i]<=u&&y[i]>=d)coor.push_back({x[i],y[i]});
	}
	double ans=(double)100*(r-l+u-d);
	if(coor.size()==0){
		cout<<fixed<<setprecision(15)<<ans<<endl;
		return 0;
	}
	sort(coor.begin(),coor.end());
	lis[lisc++]=coor[0].second;
	for(int i=1;i<coor.size();i++){
		if(coor[i].second>lis[lisc-1]){
			lis[lisc++]=coor[i].second;
			continue;
		}
		int l=0,r=lisc-1;
		while(l<r){
			int mid=(l+r)/2;
			if(coor[i].second<lis[mid]){
				r=mid;
			}else{
				l=mid+1;
			}
		}
		lis[l]=coor[i].second;
	}
	ans+=(double)lisc*5*pi-(double)20*lisc;
	if(lisc==min(r-l+1,u-d+1)){
		ans+=(double)1*5*pi;
	}
	cout<<fixed<<setprecision(15)<<ans<<endl;
	return 0;
}

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

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

  ll rn = sqrtl(n);
  ll ans = 1e18;
  for (int i = 1; i <= rn; i++) {
    if (n % i != 0) continue;
    ll c = i + n / i - 2;
    ans = min(ans, c);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>


int main(){

    int n,left = 0,right = 0;
    scanf("%d", &n);
    char str[10000];
    scanf("%s", str);
    int mid = n/2;
    if(n % 2 != 0){
    puts("No");
    return 0;
    }
for(int i= 0; i < mid ; i++ ){
    left += str[i];
}
for(int i = mid; i < n; i++){
    right += str[i];
}

if(right == left){
    printf("Yes\n");

}else {
    printf("No\n");
}

    return 0;
}

Measured memory_bytes: 1644
N = int(input())
A = list(map(int, input().split()))

mi = min(A)
ma = max(A)

ans = 10**9

for k in range(mi, ma+1):
  tmp = 0
  for a in A:
    tmp += abs(a - k) ** 2

  if ans > tmp:
    ans = tmp

print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<math.h>
#include<algorithm>
#define ll long long int
#define FOR(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n)

using namespace std;

int main(){
	int n, temp = 0;
	cin >> n;
	if(n % 10 == 0){
		cout << 10 << endl;
	}else{
		REP(i,5){
			temp += n % 10;
			n /= 10;
		}
		cout << temp << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>

typedef long double ld;
typedef long long ll;

using namespace std;

int main() {
	string s;
	cin >> s;
	if (s[2] == s[3] && s[4] == s[5]) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 3632
n,m = map(int,input().split())
s = [int(input()) for i in range(m)]
if m == 0:
    s1 = 0
else:
    s1 = s[0]
p = 0 

lis = [0 for i in range(n+1)]
lis[0] = 1
if s1 == 1:
    lis[1] = 0
    p += 1
    if p > m - 1:
        pass
    else:
        s1 = s[p]
else:
    lis[1] = 1

if n == 1:
    print(lis[1])
else:
    for i in range(2,n+1):
        if s1 == i:
            lis[i] = 0
            p += 1
            if p > m - 1:
                continue
            else:
                s1 = s[p]
        else:
            lis[i] = lis[i-1] + lis[i-2]
    print(lis[n]%1000000007)

Measured memory_bytes: 470068
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef pair < int , int > Pi;
typedef pair < int , Pi > Pii;
#define fr first
#define sc second

int M, N, D, ns, nc, nj;
char temp['z'+1],o;
int mas[20][20];
int go[20][20][20][20];
bool used[20][20][101];
Pi S, G;
int dy[] = { 0, 1, 0, -1}, dx[] = { -1, 0, 1, 0};

bool isover(int y, int x){
  return y < 0 || y >= M || x < 0 || x >= N;
}

bool isred(int y, int x, int time, bool istate){
  return ~mas[y][x] && !istate ^ time / mas[y][x] & 1;
}

int Dijkstra(){
  fill_n(**used, 20 * 20 * 101, false);
  priority_queue< Pii , vector< Pii > , greater< Pii > > que;
  que.push(Pii( 0, S)); //時間,座標
  while(!que.empty()){
    Pii p = que.top();
    que.pop();
    if(p.sc == G) return p.fr; //ごーるついた
    if(used[p.sc.fr][p.sc.sc][p.fr]++) continue;
    for(int i = 0 ; i < 4 ; i++ ){
      int ny = p.sc.fr + dy[i], nx = p.sc.sc + dx[i];
      if(isover(ny,nx)) continue; //そといった
      if(go[p.sc.fr][p.sc.sc][ny][nx] == -1) continue; //工事中
      int nexttime = p.fr + D + go[p.sc.fr][p.sc.sc][ny][nx];
      if(isred(ny, nx, nexttime, i & 1)) continue; //交差点に侵入不可
      que.push(Pii(nexttime, Pi( ny, nx)));
    }
  }
  return -1;
}


int main(){

  for(int i = 'a', j = 1 ; i <= 'z' ; i++, j++ ){ //まっぷてきなかんじ
    temp[i] = j;
  }


  while( cin >> M >> N, M){

    fill_n(*mas, 400, -1);
    fill_n(***go, 20 * 20 * 20 * 20, 0);

    cin >> D;
    cin >> ns;
    for(int i = 0 ; i < ns ; i++ ){
      char h;
      int v, k;
      cin >> h >> o >> v >> k;
      mas[temp[h] - 1][v - 1] = k;
    }

    cin >> nc;
    for(int i = 0 ; i < nc ; i++ ){
      char h1, h2;
      int v1, v2;
      cin >> h1 >> o >> v1 >> h2 >> o >> v2; //入力面倒くさいね
      go[temp[h1] - 1][v1 - 1][temp[h2] - 1][v2 - 1] = -1;
      go[temp[h2] - 1][v2 - 1][temp[h1] - 1][v1 - 1] = -1;
    }

    cin >> nj;
    for(int i = 0 ; i < nj ; i++ ){
      char h1, h2;
      int v1, v2, d;
      cin >> h1 >> o >> v1 >> h2 >> o >> v2 >> d;
      go[temp[h1] - 1][v1 - 1][temp[h2] - 1][v2 - 1] = d;
      go[temp[h2] - 1][v2 - 1][temp[h1] - 1][v1 - 1] = d;
    }

    char h1, h2;
    int v1, v2;
    cin >> h1 >> o >> v1 >> h2 >> o >> v2;
    S = Pi( temp[h1] - 1, v1 - 1);
    G = Pi( temp[h2] - 1, v2 - 1);

    cout << Dijkstra() << endl;
  }
}

Measured memory_bytes: 1888
from math import sqrt, pow

def get_distance(xi, yi, xj, yj):
  return sqrt(pow(xi - xj, 2) + pow(yi - yj, 2))

def solve():
  n = int(input())
  locations = [list(map(int, input().split())) for _ in range(n)]
  
  distance = 0
  
  for xi, yi in locations:
    for xj, yj in locations:
      distance += get_distance(xi, yi, xj, yj)
  
  return distance / n

print(solve())

Measured memory_bytes: 3060
// input macro
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        a: usize,
        b: usize,
    }
    if (a + b) % 2 == 0 {
        println!("{}", (a + b) / 2);
    } else {
        println!("IMPOSSIBLE")
    }
}


Measured memory_bytes: 4352
#include <iostream>
#include <bitset>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>

using namespace std;

int main()
{
	long long n;
	string s = "YES";
	cin >> n;
	vector<long long> a(n);

	for (long long i = 0; i < n; i++)
		cin >> a[i];

	sort(a.begin(), a.end());

	for (long long i = 0; i < n-1; i++)
	{
		if (a[i] == a[i + 1])
		{
			s = "NO";
			break;
		}
	}

	cout << s << endl;
}


Measured memory_bytes: 1792
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        String str = sc.next();
        
        int[] tmp = new int[3];
        tmp[0] = Integer.parseInt(String.valueOf(str.charAt(0)));
        tmp[1] = Integer.parseInt(String.valueOf(str.charAt(2)));
        tmp[2] = Integer.parseInt(String.valueOf(str.charAt(3)));
        
        long tmpa = a * tmp[0];
        long tmpb = a * tmp[1];
        long tmpc = a * tmp[2];
        
        long tmpb2 = tmpb / 10;
        long tmpc2 = tmpc / 100;
        
        long tmpb3 = (tmpb % 10) * 10;
        long tmpc3 = tmpc % 100;
        
        long tmpx = (tmpb3 + tmpc3) / 100;
        System.out.println(tmpa + tmpb2 + tmpc2 + tmpx);
    }
}


Measured memory_bytes: 35812
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;

/* typedef */

/* global variables */

int xs[MAX_N], dxs[MAX_N];

/* subroutines */

/* main */

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

  while (tn--) {
    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i++) cin >> xs[i];
    sort(xs, xs + n);

    for (int i = 0; i < n - 1; i++) dxs[i] = xs[i + 1] - xs[i];
    sort(dxs, dxs + n - 1);

    int sum = 0;
    for (int i = 0; i < n - k; i++) sum += dxs[i];

    cout << sum << endl;
  }

  return 0;
}

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

int main()
{
	long long N, res = 0;
	cin >> N;
	vector<int> a(N);
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < N; i++) {
		if (a[a[i] - 1] - 1 == i)
			res++;
	}
	cout << (res / 2) << endl;
	return 0;
}


Measured memory_bytes: 768
#include <iostream>

using namespace std;

long get_score(char h, int R, int S, int P){
    if(h == 'r') return P;
    if(h == 's') return R;
    if(h == 'p') return S;
    else return 0;
}

int main(){
    long N, K;
    cin >> N >> K;
    int R, S, P;
    cin >> R >> S >> P;
    string T;
    cin >> T;
    long ans = 0;
    for(int i=0; i<N; i++){
        if(i<K) ans += get_score(T[i], R, S, P);
        else{
            if(T[i] == T[i-K]){
                T[i] = 'x';
            }
            else{
                ans += get_score(T[i], R, S, P);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
//#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const ll INF = 10000000000000000;
const ll mod = 1000000007;
//printf("%.10f\n", n);
signed main() {
	ll n = 0, m, a = 0, b = 0, cnt = 0, ans = 0; cin >> n >> a >> b;
	if (a % 2 == b % 2) { cout << "Alice" << endl; }
	else { cout << "Borys" << endl; }
	cin >> n; return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define all(v) (v).begin(),v.end()
const ll inf=(1e18);
const ll mod=1000000007;
const ll mod2=998244353;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int h,w;cin>>h>>w;
vector<vector<int>> a(h,vector<int>(w));
int n;cin>>n;
vector<int> cl(n);
int j=0,k=0;
for(int i=0;i<n;i++)cin>>cl[i];
for(int i=0;i<n;i++){
    while(cl[i]--){
             a[j][k]=i+1;
             if(j%2==0)k++;
             else k--;
             if(k<0){j++;k=0;}
             if(k==w){j++;k=w-1;}
    }
}
for(int i=0;i<h;i++){
  for(int j=0;j<w;j++){
      cout<<a[i][j]<<" ";
  }
  cout<<endl;
}
}

Measured memory_bytes: 384
#include<stdio.h>
int main(void)
{
	int a,b;
	scanf("%d %d",&a,&b);
	if(a < b){
		printf("a < b\n");
	}else if(a > b){
		printf("a > b\n");
	}else{
		printf("a == b\n");
	}
	return 0;
}

Measured memory_bytes: 580
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define debug(var) do{cout << #var << " : "; view(var);}while(0)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
template<class T> void view(T e) {cout << e << endl;}
template<class T> void view(const vector<T> &v) {for(const auto &e : v){cout << e << " ";} cout << endl;}
template<class T> void view(const vector<vector<T>> &vv) {for(const auto &v : vv){view(v);}}
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    int n; cin >> n;
    vint l(2*n);
    rep(i,2*n) cin >> l[i];
    sort(all(l));
    int ans = 0;
    for (int i = 0; i < 2*n; i += 2) ans += l[i];
    cout << ans << endl;
}

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

int main()
{
    int a,b,c;
    cin >> a >> b >> c ;
    if( a > c ) { cout << "NO" ;}
    else if( a < c && a + b < c) { cout << "NO" ;}
    else { cout << "YES" ;}
}


Measured memory_bytes: 3640
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;


#define NUM 1120

int main(){
	int table[NUM],limit;

	for(int i=0; i < NUM;i++)table[i] = 1;
	table[0] = 0;
	table[1] = 0;

	limit = sqrt(NUM);

	for(int i=2;i<=limit;i++){
		if(table[i] == 1){
			for(int k=2*i;k < NUM; k += i){
				table[k] = 0;
			}
		}
	}

	int prime_table[NUM],index = 0;

	for(int i = 2; i < NUM; i++){
		if(table[i] == 1){
			prime_table[index++] = i;
		}
	}

	int*** dp = new int**[15];
	for(int i = 0; i < 15; i++){
		dp[i] = new int*[index];
		for(int k = 0; k < index; k++){
			dp[i][k] = new int[1121];
		}
	}

	for(int i = 0; i < 15; i++){
		for(int k = 0; k < index; k++){
			for(int p = 0; p < 1121; p++)dp[i][k][p] = 0;
		}
	}

	for(int i = 0; i < index; i++){
		dp[1][i][prime_table[i]] = 1;
	}

	for(int k = 2; k <= 14; k++){
		for(int i = 1; i < index; i++){
			for(int p = 0; p <= i-1; p++){
				for(int a = prime_table[i]+1; a <= 1120; a++){
					dp[k][i][a] += dp[k-1][p][a-prime_table[i]];
				}
			}
		}
	}

	int A,B,sum;

	while(true){
		scanf("%d %d",&A,&B);
		if(A == 0 && B == 0)break;

		sum = 0;

		for(int i = 0; i < index; i++)sum += dp[B][i][A];

		printf("%d\n",sum);

	}

	return 0;
}

Measured memory_bytes: 14964
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define DEBUGP(val) cerr << #val << "=" << val << "\n"

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;

/*
 * Union-Find tree
 * header requirement: vector
 */
class UnionFind {
private:
  std::vector<int> disj;
  std::vector<int> rank;
public:
  UnionFind(int n) : disj(n), rank(n) {
    for (int i = 0; i < n; ++i) {
      disj[i] = i;
      rank[i] = 0;
    }
  }
  int root(int x) {
    if (disj[x] == x) {
      return x;
    }
    return disj[x] = root(disj[x]);
  }
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) {
      return;
    }
    if (rank[x] < rank[y]) {
      disj[x] = y;
    } else {
      disj[y] = x;
      if (rank[x] == rank[y]) {
	++rank[x];
      }
    }
  }
  bool is_same_set(int x, int y) {
    return root(x) == root(y);
  }
};

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int v, d;
  while (cin >> v >> d) {
    int a = 1, b = 2;
    UnionFind uf(v + 1);
    VI val(v + 1);
    REP(i, 1, v + 1) {
      val[i] = b;
      int c = (a + b) % 1001;
      a = b; b = c;
    }
    REP(i, 1, v + 1) REP(j, i + 1, v + 1) if (abs(val[i] - val[j]) < d)
      uf.unite(i, j);
    set<int> r;
    REP(i, 1, v + 1) r.insert(uf.root(i));
    cout << r.size() << endl;
  }
}



Measured memory_bytes: 3248
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;

int main() {
	LL a;
	LL b;
	LL ret=0;
	cin >> a >> b;
	ret+=a;
	a-=b;
	//cout << ret << endl;
	while(a){
		LL r=b%a;
		//cout << b << ", " << a << ": ";
		//cout << b/a*a*2 << endl;
		ret+=(b/a)*a*2;
		if(r==0){
			ret-=a;
		}
		b=a;
		a=r;
	}
	cout << ret << endl;
}


Measured memory_bytes: 256
MODE = "stdio"
require 'matrix'
line = Array.new

if(defined? MODE)
  line = STDIN.read.split("\n")
else
  tmp = 'xyz
  3
  print 0 2
  replace 0 2 abc
  print 0 2'.split("\n")
  tmp.each{|s|
    line << s.strip
  }
end
str=line[0]
n = line[1].to_i

(2..n+1).each do |m|
  c,a,b,p = line[m].split(" ")
  a = a.to_i
  b = b.to_i

  if c=="print"
    puts str[a..b]
  elsif c=="reverse"
    str[a..b] = str[a..b].reverse
  elsif c=="replace"
    str[a..b] = p
  end
end

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

typedef long long ll;
typedef vector<ll> vint;
typedef vector< vector<ll> > vvint;

#define rep(i,n) for(ll i=0;i<n;i++)
#define repf(i,f,n) for(ll i=f;i<n;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define mp make_pair
#define mt make_tuple
#define ALL(obj) (obj).begin(), (obj).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; }

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

using T = tuple<ll,ll,ll>;
using P = pair<ll,ll>;

void solve(){
    ll n; cin>>n;
    vint k(n),l(n),r(n);
    rep(i,n) cin>>k[i]>>l[i]>>r[i];
    ll ans = 0;

    vector<P> dk[2];
    rep(i,n){
        ans += r[i];
        ll d = l[i] - r[i];
        if(d>=0){
            dk[0].emplace_back(d, k[i]);
        }else{
            dk[1].emplace_back(-d, k[i]);
        }
    }

    sort(ALL(dk[0]), greater<P>());
    sort(ALL(dk[1]), greater<P>());

    set<ll> s[2];
    rep(i,n) {
        s[0].insert(-i);
        s[1].insert(i);
    }


    // positive
    for(auto p:dk[0]){
        ll d,k; tie(d,k) = p;
        k--;
        auto it = s[0].lower_bound(-k);
        if(it == s[0].end()){
            // 何もしない
        }else{
            // 左側
            ans += d;
            s[0].erase(it);
        }
    }

    for(auto p:dk[1]){
        ll d,k; tie(d,k) = p;
        auto it = s[1].lower_bound(k);
        if(it == s[1].end()){
            ans -= d;
        }else{
            s[1].erase(it);
        }
    }

    cout<<ans<<endl;



}

int main() {
    cout<<fixed<<setprecision(10);

    ll t; cin>>t;

    while(t>0){
        solve();
        t--;
    }



    return 0;

}

Measured memory_bytes: 29804
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
using namespace std;



int main() {
//    cout << setprecision(10);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    ll n, k;
    cin >> n >> k;
    ll a[n], smaller[n], inv[n];
    for (ll i = 0; i < n; i++) cin >> a[i];

    for (ll i = 0; i < n; i++) {
        ll sm = 0;
        for (ll e : a) {
            if (e < a[i]) sm++;
        }
        smaller[i] = sm;
        sm = 0;
        for (ll j = i + 1; j < n; j++) {
            if (a[j] < a[i]) sm++;
        }

        inv[i] = sm;
    }


    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        ll t = (k * k - k * (k + 1) / 2) % mod;
        ans = (ans + (inv[i] * k) % mod + (smaller[i] * t) % mod) % mod;
    }

    cout << ans;

}



Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <queue>
#include <stack>
using namespace std;

typedef struct Vector{
    int x;
    int y;
} Vector;

double outerProduct(Vector v1, Vector v2);

int main(){
    int pointNum ;
    queue<double> results;
    queue<Vector> points;
    stack<Vector> vecs;
    int x,y;
    Vector v1,v2;
    double area;
    
    scanf("%d", &pointNum);
    while (pointNum != 0) {
        for (int i = 0; i < pointNum; i++) {
            cin>>x>>y;
            points.push({x,y});
        }
        points.push(points.front());
        
        v1 = points.front();
        points.pop();
        while(!points.empty()){
            v2 = points.front();
            vecs.push({v2.x-v1.x, v2.y-v1.y});
            v1 = v2;
            points.pop();
        }
        
        //calculate the area
        v1 = vecs.top();
        vecs.pop();
        v2 = vecs.top();
        vecs.pop();
        
        area = 0;
        
        while (!vecs.empty()) {
            area += outerProduct(v1, v2);
            vecs.push({v1.x+v2.x, v1.y+v2.y});
            v1 = vecs.top();
            vecs.pop();
            v2 = vecs.top();
            vecs.pop();
        }
        
        results.push(area);
        
        cin>>pointNum;
        
    }
    
    int i = 1;
    while (!results.empty()) {
        area = results.front();
        printf("%d %.1f\n", i, area);
        results.pop();
        i++;
    }
    
    return 0;
}

double outerProduct(Vector v1, Vector v2){
    double c = -(v2.x * v1.y - v1.x * v2.y);
    return c / 2;
}

Measured memory_bytes: 3172
#include <iostream>
using namespace std;
int main(){
  string str;
  cin >> str;

  if((str[0]==str[1]&&str[0]==str[2])||(str[1]==str[2]&&str[2]==str[3])){
        cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <functional>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
using namespace std;
// #define int long long
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = (((1<<30)-1)<<1)+1;
const int nINF = 1<<31;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<char, int> pci;

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



const int N = 1e5+10;
int n, m;
ll ans[N];
pii e[N];
multiset<int> ms;

// Initialize with std::iota(parent, parent+n+1, 0), std::fill(sz, sz+n+1, 1);

int parent[N];
int sz[N];

// Uses path compression
int find(int x) {return parent[x] = (x == parent[x] ? x : find(parent[x]));}

bool disjoint(int x, int y) {return find(x) != find(y);}

void join(int x, int y) {
	if (!disjoint(x, y)) return;
	int newPar = find(x), newChild = find(y);
	sz[newPar] += sz[newChild];
	parent[newChild] = newPar;
}

int dsuSize(int x) {return sz[find(x)];}

ll choose2(ll x) {return (x*(x-1))/2;}

signed main() {
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(7);
    cin >> n >> m;
    REP(i, m) cin >> e[i].first >> e[i].second;
    std::iota(parent, parent+n+1, 0), std::fill(sz, sz+n+1, 1);
    FOR(i, 1, n) ms.insert(1);
    ans[m] = choose2(n);
    FORD(i, m-1, 0) {
    	int a = e[i].first, b = e[i].second;
		ans[i] = ans[i+1];
    	if(disjoint(a, b)) {
    		ll sza = dsuSize(a), szb = dsuSize(b);
    		ans[i] -= sza*szb;
    	}
    	join(a, b);
    }
    FOR(i, 1, m) cout << ans[i] << endl;

    return 0;
}

// Easy things to check:
// - LONG LONGS (WA)
// - const int N is correct (WA, RTE)
// - .size()-k underflow (WA, RTE, TLE)
// - small n edge cases (WA)

// Rare mistakes made in the past:
// - division by 0 (WA)
// - integer division (WA)
// - setprecision (WA)
// - INF not big enough using ll (WA)
// - setting max to 0 instead of -INF/min to 0 instead of INF (WA)
// - outputting debug (WA)
// - allocating too much memory (locRTE, MLE)
// - stack size (locRTE)
// - round announcements (WA)
// - multiset::erase (WA)



Measured memory_bytes: 8320
#include<bits/stdc++.h>
typedef long long ll;

using namespace std;

int main(){
	int n;
	cin>>n;
	int a[n];
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	ll dp[n];
	dp[0]=0;
	dp[1]=abs(a[1]-a[0]);
	for(int i=2; i<n; i++){
		dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]), dp[i-2]+abs(a[i]-a[i-2]));
	}
	cout<<dp[n-1];
	return 0;
}


Measured memory_bytes: 4776
S = input()
N = len(S)

answer = 0
for i in range(2 ** (N - 1)):
    tmp = S[0]
    for j in range(N - 1):
        if (i >> j) & 1:
            tmp += "+" + S[j + 1]
        else:
            tmp += S[j + 1]
    answer += eval(tmp)

print(answer)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007LL;
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL)
//________________________________________
const int N = 100005;
vector<int> dp[N];
bool vis[N];
void dfs(int i)
{
       vis[i] = true;
       for(int k : dp[i])
       {
              if(!vis[k])dfs(k);
       }
}
signed main()
{
       int n,m;
       cin>>n>>m;
       memset(vis,false,sizeof vis);
       while(m--)
       {
              int a,b;
              cin>>a>>b;
              --a;--b;
              dp[a].push_back(b);
              dp[b].push_back(a);

       }
       int ans = -1;
       for(int i = 0 ; i < n ; i++){
              if(!vis[i]){
                     dfs(i);
                     ans++;
              }
       }
       cout<<ans<<endl;
}


Measured memory_bytes: 9644
function main(input){
    args = input.split("\n");
    a = parseInt(args[0],10);
    b = parseInt(args[1],10);
    c = parseInt(args[2],10);
    d = parseInt(args[3],10);
    p = 0;
    for (var i = 0; i <= a ; i ++) {
        if (500 * i > d) break;
        for (var j = 0; j <= b ; j ++) 
        {
            if (500 * i + 100 * j > d) break;
            for (var k = 0; k <= c ; k ++) 
            {
                if ((500 * i + 100 * j  + 50 *k )== d) p +=1;
            }
        }
    }
    console.log(p)
}
main(require('fs').readFileSync('/dev/stdin', {encoding:'utf8'}))


Measured memory_bytes: 7372
#include<cstdio>
#include<vector>
#include<map>
#define F first
#define S second
using namespace std;
typedef pair<int, int> P;
int main(void){
  int n, m, ans = 0;
  bool x[100010];
  vector<P> v;
  for( ; ; ){
    scanf("%d", &n);
    if(!n) break;
    for(int i = 1;i <= n; i++){
      scanf("%d", &m);
      x[i] = m;
    }
    ans = 0; v.clear();
    v.push_back(make_pair(1, x[1]));
    for(int i = 2;i <= n; i++){
      if(x[i] == v.back().S) v.back().F++;
      else if(i % 2) v.push_back(make_pair(1, x[i]));
      else{
	m = v.back().F; v.pop_back();
	if(v.empty()) v.push_back(make_pair(m + 1, x[i]));
	else v.back().F += m + 1;
      }
    }
    for(int i = 0;i < v.size(); i++){
      if(!v[i].S) ans += v[i].F;
    }
    printf("%d\n", ans);
  }
}


Measured memory_bytes: 1128
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
using Ml = map<ll, ll>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  ll a, b, h;
  cin >> a >> b >> h;

  cout << (a+b) * h / 2 << endl;

  return 0;
}


Measured memory_bytes: 3608
from itertools import accumulate

class SegTree:  # 0-index !!!
    """
    fx: モノイドXでの二項演算
    ex: モノイドXでの単位元
    init(seq, fx, ex): 配列seqで初期化 O(N)
    update(i, x): i番目の値をxに更新 O(logN)
    query(l, r): 区間[l,r)をfxしたものを返す O(logN)
    get(i): i番目の値を返す
    show(): 配列を返す
    """

    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        # build
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, i, x):  # O(log(n))
        i += self.size
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):  # l = r の場合はたぶんバグるので注意
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  # 交換法則を仮定しない(順序大事に)
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)

    def get(self, i):
        return self.tree[self.size + i]

    def show(self):
        return self.tree[self.size: self.size + self.n]

# ---------------------- #

n, c = (int(x) for x in input().split())
X = []
V = []
D = []
prev_x = 0
for _ in range(n):
    x, v = (int(x) for x in input().split())
    X.append(x)
    D.append(x - prev_x)
    V.append(v)
    prev_x = x
D.append(c - X[-1])
rev_D = list(reversed(D))
rev_V = list(reversed(V))

ans = 0
# 時計回り
A = [0] * n
for i in range(n):
    A[i] = V[i] - D[i]
acc_A = list(accumulate(A))
ans = max(ans, max(acc_A))

# 反時計回り
B = [0] * n
for i in range(n):
    B[i] = rev_V[i] - rev_D[i]
acc_B = list(accumulate(B))
ans = max(ans, max(acc_B))

# 時計回りからの反時計回り i個まで食べて向きを変える
seg_B = SegTree(acc_B, fx=max, ex=-10**18)
tmp = 0
for i in range(n - 1):
    tmp_cal = acc_A[i] - X[i]  # 食べて原点まで戻った時点のカロリー
    tmp = max(tmp, tmp_cal + seg_B.query(0, n-i-1))
ans = max(ans, tmp)

# 反時計回りからの時計回り
seg_A = SegTree(acc_A, fx=max, ex=-10**18)
tmp = 0
for i in range(n - 1):
    tmp_cal = acc_B[i] - (c - X[-i - 1])  # 食べて原点まで戻った時点のカロリー
    tmp = max(tmp, tmp_cal + seg_A.query(0, n-i-1))
ans = max(ans, tmp)

print(ans)


Measured memory_bytes: 109080
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main (){
	vector<string>X(10);
    X[0] ="pon";
  	X[1] ="pon";
  	X[2] ="hon";
    X[3] ="bon";
 	X[4] ="hon";
    X[5] ="hon";
    X[6] ="pon";
    X[7] ="hon";
    X[8] ="pon";
    X[9] ="hon";
  	int Y;
  	cin >> Y;
    int S = Y%10;
  	cout << X[S] <<endl;
}

Measured memory_bytes: 3580
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

static int
is_prime(int e) {
  int i;

  if (e < 2) return 0;
  if (e == 2) return 1;
  if (e % 2 == 0) return 0;

  for (i = 3; i * i <= e; i += 2) {
    if (e % i == 0) return 0;
  }
  return 1;
}

int main(int argc, char **argv) {
  int n, e, ret, cnt;

  ret = scanf("%d", &n);
  if (errno != 0) perror("scanf: n");
  if (ret < 1) exit(1);

  cnt = 0;
  while (1) {
    ret = scanf("%d", &e);
    if (errno != 0) perror("scanf: e");
    if (ret < 1) break;
    if (is_prime(e)) ++cnt;
  }

  printf("%d\n", cnt);
  exit(0);
}


Measured memory_bytes: 2108
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<char, char> PC;

int n, m;
char pc[100000][2], c;
string s;

int main(){
	while (cin >> n&&n){
		REP(i, n){
			cin >> pc[i][0] >> pc[i][1];
		}
		cin >> m;
		REP(i, m){
			cin >> c;
			REP(j, n){
				if (c == pc[j][0]){
					c = pc[j][1];
					break;
				}
			}
			s += c;
		}
		cout << s << endl;
		s.clear();
	}
}

Measured memory_bytes: 1328
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <numeric>
#include <climits>
#include <map>
#define LIM 1000000007
#define ll long long
using namespace std;
int main() {
  ll n;
  map <ll, ll> mp;
  cin >> n;
  for (ll i = 1; i <= n; i++) {
    ll k = i;
    for (ll m = 2; m <= i; m++) {
      while (k % m == 0) {
        mp[m]++;
        k /= m;
      }
    }
  }
  ll ans = 1;
  for (auto itr = mp.begin(); itr != mp.end(); itr++) {
    ans *= (itr->second + 1);
    ans %= LIM;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
	int N; cin >> N;
	string S; cin >> S;
	int depth = 0;
	rep(i, S.length()) {
		if (S[i] == '(') {
			if (depth < 0) {
				rep(i, -depth) S = '(' + S;
				i += -depth;
				depth = 0;
			}
			depth++;
		}
		else depth--;
		// if (depth < 0) S.insert(S.begin() + i, '(');
	}
	if (depth < 0) {
		rep(i, -depth) S = '(' + S;
	} 
	rep(i, depth) S += ")";
	cout << S << endl;


    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int a, b, ans = 0, i;
    
    scanf("%d %d", &a, &b);
    
    for(i = 0; i < 2; i++){
        if(a >= b){
            ans = ans + a;
            a = a - 1;
        }else if(a <= b){
            ans = ans + b;
            b = b - 1;
        }
    }
    printf("%d\n", ans);
    
}


Measured memory_bytes: 1732
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int di[] = {0, 0, 1, -1};
constexpr int dj[] = {1, -1, 0, 0};

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

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

    if ((a < c && c < b) || (b < c && c < a))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

mod = 10**9+7
N, A, B = map(int, input().split())
ans = pow(2, N, mod) - 1 - combination(N, A) - combination(N, B)
ans %= mod
print(ans)


Measured memory_bytes: 9132
#include <stdio.h>
#include <stdlib.h>

int mas[4][4];
int cpy[4][4];

void input() {
  int i, j;
  for(i = 0; i < 4; i++)
    for(j = 0; j < 4; j++)
      scanf("%d", &mas[i][j]);
}

void output() {
  int i, j;
  for(i = 0; i < 4; i++) {
    for(j = 0; j < 4; j++) printf("%3d", mas[i][j]);
    puts("");
  }
}

void copy(int m[4][4], int t[4][4]) {
  int i, j;

  for(i = 0; i < 4; i++)
    for(j = 0; j < 4; j++) m[i][j] = t[i][j];
}

int calc() {
  int i, sum = 0;
  for(i = 0; i < 16; i++) {
    int v = mas[i/4][i%4];
    if(v) {
      v--;
      sum += abs(i/4-v/4)+abs(i%4-v%4);
    }
  }
  return sum;
}

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

void swap(int *a, int *b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

int is_in(int x, int y) {
  return 0<=x&&x<4&&0<=y&&y<4;
}

int dfs(int x, int y, int p, int dep, const int lim) {
  int i, h = calc();
  //output();
  if(h == 0) return dep;
  //printf("%d %d %d\n", h, lim, p);
  if(dep+h > lim) return -1;

  for(i = 0; i < 4; i++) {
    int nx = x+dx[i], ny = y+dy[i], res;
    if(~p && i == (p+2)%4) continue;
    if(!is_in(nx, ny)) continue;
    swap(&mas[y][x], &mas[ny][nx]);
    res = dfs(nx, ny, i, dep+1, lim);
    if(~res) return res;
    swap(&mas[y][x], &mas[ny][nx]);
  }

  return -1;
}

void get_empty(int *x, int *y) {
  int i, j;
  for(i = 0; i < 4; i++) {
    for(j = 0; j < 4; j++) {
      if(!mas[i][j]) {
	*x = j;
	*y = i;
	return;
      }
    }
  }
}

int solve() {
  int x, y, lim, ans;
  get_empty(&x, &y);
  for(lim = 0; lim < 50; lim++) {
    copy(cpy, mas);
    if((ans = dfs(x, y, -1, 0, lim)) != -1) return ans;
    copy(mas, cpy);
  }
  return -1;
}

int main() {
  input();
  printf("%d\n", solve());
  return 0;
}

Measured memory_bytes: 600