akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <queue>
#include <map>
#include <deque>
#include <algorithm>
#include <set>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <cstring>
#include <climits>
#include <iostream>
 
 
#define ll long long
#define p 1000000007
using namespace std;
//const ll MOD = (int) 10e9 + 7;
 
ll dp[100001][2];
vector<vector<ll>>adj;
/*
ll dfs(ll node)
{
    if (dp[node] != -1)
        return dp[node];
    ll ans = 0;
 
    if (adj[node].size() == 0)
        return 2;
 
    for (int i = 0; i < adj[node].size(); i++) {
        ans = max(dfs(adj[node][i]) + 1, ans);
 
    }
 
 
    return dp[node] = ans;
}
*/
ll dfsColor(ll node, ll parent, ll color)
{
    if (adj[node].size() == 1 && adj[node][0] == parent)
        return dp[node][color] = 1;
 
    if (dp[node][color] != -1)
        return dp[node][color] % p;
 
    ll ans = 1;
    for (ll i = 0; i < adj[node].size(); i++)
    {
        if (adj[node][i] != parent)
        {
            ll x,y;
            x = y = 0;
            if (color == 1)
                x = dfsColor(adj[node][i], node, 0) % p;
            y = dfsColor(adj[node][i], node, 1) % p;
            ans *= (x + y);
            ans %= p;
        }
    }
    return dp[node][color] = ans;
}
 
ll factorial(ll n)
{
    if (n == 1 || n == 0)
        return 1;
    return  n * factorial(n - 1);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    ll n;
    cin >> n;
    for (int i  = 0; i < n; i++)
    {
        vector<ll>temp;
        adj.push_back(temp);
    }
    for (int i = 0; i < n - 1; i++)
    {
        ll x,y;
        cin >> x >> y;
        x--;
        y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    if (n == 1)
        cout << 2;
    else
    {
        for (ll i = 0; i < 100001; i++)
            for (ll j = 0; j < 2; j++) dp[i][j] = -1;
 
        ll ans = 1;
        for (ll i = 0; i < n; i++)
        {
            if (dp[i][0] == -1)
                ans *= ((dfsColor(0,0,0) % p) + (dfsColor(0,0,1) % p)) % p;
        }
        cout << ans % p;
    }
    /*std::cout<<std::fixed;
    std::cout<<std::setprecision(10)<<ans;*/
             //   dp[i][i + 1 + j] = min(dp[i][i + j] + (pre[i + j + 2] - pre[i]),dp[i + 1][i + 1 + j] + (pre[i + j + 2] - pre[i]));
 
    return 0;
}

Measured memory_bytes: 14192
n = int(input())
a = [int(input()) for _ in range(n)]
A = [0]*n
i = 0
ok = False
cnt = 0
for _ in range(n):
  cnt += 1
  A[i] = 1
  if a[i] == 2: 
    ok = True
    break
  i = a[i]-1
  if A[i] == 1: break
print(cnt if ok else -1)

Measured memory_bytes: 7852
N = int(input())
S = input()


abc = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
abc_map = {}
for i, c in enumerate(abc):
    abc_map[c] = i

sb = ''
for n in list(S):
    i = (abc_map[n] + N) % len(abc)
    sb += abc[i]

print(sb)

Measured memory_bytes: 3060
#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 D, T, S;
  	cin >> D >> T >> S;
  
  	if (D>T*S) {
      cout << "No" << endl;
    } else {
      cout << "Yes" << endl;
    }
  	
    return 0;
}

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

signed main(){
	int n;
	scanf("%d", &n);
	if(n % 2 == 1){
		cout << (n - 1) * (n - 1) / 2 << endl;
		for(int i = 1; i < n; i++){
			for(int j = i + 1; j <= n; j++){
				if(i + j != n){
					cout << i << " " << j << endl;
				}
			}
		}
	}
	else{
		cout << n * (n - 2) / 2 << endl;
		for(int i = 1; i < n; i++){
			for(int j = i + 1; j <= n; j++){
				if(i + j != n + 1) cout << i << " " << j << endl; 
			}
		}
	}
}

Measured memory_bytes: 3712
import java.util.Scanner;

public class Main {
    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final long q = scanner.nextInt();
        final long h = scanner.nextInt();
        final long s = scanner.nextInt();
        final long d = scanner.nextInt();
        final long n = scanner.nextInt();

        final long l1 = Math.min(s, Math.min(h * 2, q * 4));
        final long l2 = Math.min(l1 * 2, d);

        if (n % 2 == 0) {
            System.out.println(n / 2 * l2);
        } else {
            System.out.println(n / 2 * l2 + l1);
        }
    }
}


Measured memory_bytes: 23124
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
	string S;
	cin >> S;
	int S1, S2;
	char check1, check2;
	int last = 0;
	if (S[0] == '0'&&S[1] == '0') {
		check1 = 'y';
	}
	else if(S[0] == '0'&&S[1] != '0'){
		check1 = 'r';
	}
	else if (S[0] == '1') {
		if (S[1] == '0' || S[1] == '1' || S[1] == '2') {
			check1 = 'r';
		}
		else {
			check1 = 'y';
		}
	}
	else {
		check1 = 'y';
	}

	if (S[2] == '0'&&S[3] == '0') {
		check2 = 'y';
	}
	else if (S[2] == '0'&&S[3] != '0') {
		check2 = 'r';
	}
	else if (S[2] == '1') {
		if (S[3] == '0' || S[3] == '1' || S[3] == '2') {
			check2 = 'r';
		}
		else {
			check2 = 'y';
		}
	}
	else {
		check2 = 'y';
	}
	
	if (check1 == 'r'&&check2 == 'r') {
		cout << "AMBIGUOUS";
	}
	else if (check1 == 'r'&&check2 == 'y') {
		cout << "MMYY";
	}
	else if (check1 == 'y'&&check2 == 'r') {
		cout << "YYMM";
	}
	else {
		cout << "NA";
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
//bool is_prime(ll x){
//if(x<=1) return 0;
//for(int i=2;i*i<=x;i++){
//    if(x%i==0)return 0;
//}
//return 1;
//}
ll mod=1e7;
int main(){
ll x;
cin>>x;
vector<ll> v1(x+1,0);
for(ll i=1;i<=x;i++){
 for(ll j=0;j<=x;j+=i)
        v1[j]++;
}
ll total=0;
for(ll i=1;i<=x;i++){
total+=(i*(ll)v1[i]);
}
cout<<total;
}



Measured memory_bytes: 81352
//$g++ -std=c++11 Template.cpp 

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

priority_queue<int> q_descending;
priority_queue<int, vector<int>, greater<int> > q_ascending;

template <typename T>
class UnionFind {
public:
  T n;
  vector <T> d;
  UnionFind(T n) :d(n, -1) {} 
  int find(T x){
    if(d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(T x, T y){
    x = find(x);
    y = find(y);
    if(x == y) return false;
    if(size(x) < size(y)) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  int size(T v){ return -d[find(v)];}
  bool same(T x, T y){
    return find(x) == find(y);
  }
};

int p[1000000], x[1000000], y[1000000];

int
main(void){  
  ios_base::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;
  REP(i, n) cin >> p[i];
  REP(i, m) cin >> x[i] >> y[i];

  UnionFind<int> uf = UnionFind<int>(n+1);

  REP(i, m) uf.unite(x[i], y[i]);

  ll ans = 0LL;

  REP(i, n) if(uf.same(i+1, p[i])) ans++; 

  cout << ans << endl;
  
  //if(uf.unite(x[0], y[0])) cout << "success" << endl;
  //cout << uf.size(5) << endl;;
  
  return 0;
}


Measured memory_bytes: 9216
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;


	//
	int divm2(int a) {
		if(a>0) {
			return -(a/2);
		}else if(a<0){
			return (-a+1)/2;
		}else {
			return 0;
		}
	}

	String solv(int n) {
		if(n==0) {
			return "";
		}
		if(Math.abs(n)%2 == 0) {
			return solv(divm2(n))+"0";
		}else {
			return solv(divm2(n))+"1";
		}
	}

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int N = sc.nextInt();

		sc.close();

		if(N==0) {
			out.println(0);
		}else {
			out.println(solv(N));
		}

	}

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

}


Measured memory_bytes: 21844
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF (long long) 1e18//1234567890987654321
#define INF 1234567890
#define pb push_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos(-1))
#define MAXN 300006
#define MAXK 26
#define MAXX 15000006
#define ll long long int
#define ld long double
#define rep0(kk, l1, l2)for(ll kk = l1; kk < l2; kk++)
#define rep1(kk, l1, l2)for(ll kk = l1; kk <= l2; kk++)
#define foritr(itr, A) for(set<ll>::iterator itr = A.begin(); itr != A.end(); itr++)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ii++)
#define cr(x) cerr << #x << " = " << x << "\n";
#define crA(x, A) cerr << #x << " = " << A[x] << "\n";
#define spacing if(db)cout << " ";
#define mmst(x, v) memset((x), v, sizeof ((x)));
#define bg(ms) (*ms.begin())
#define ed(ms) (*prev(ms.end(), 1))
#define addedge(a, b, c, v) v[(a)].pb(pi((b), (c))); v[(b)].pb(pi((a), (c)))
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n, A[4];
int main()
{
	FOR(i,0,4) cin >> A[i];
	sort(A, A+4);
	if(A[0] == 1 && A[1] == 4 && A[2] == 7 && A[3] == 9) { cout << "YES\n"; }
	else cout << "NO\n";
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        Main m = new Main(sc);
        m.show(m.solve());
        sc.close();
    }
    
	//フィールド
    Scanner sc;
    int X;
    int Y;
    
    //入力
    Main(Scanner sc) {
        this.sc = sc;
        this.X = sc.nextInt();
        this.Y = sc.nextInt();
    }
    
    //解答処理
    private String solve() {
        String answer = "No";
        int crane = 0; //鶴の数
        int turtle = 0;//カメの数
        int total = crane + turtle;
        int total2 = X * 4; //全てカメだった場合の足の本数
        
        if (Y % 2 == 0) {
        	crane = Y -2 * X;
        	turtle = 4 * X - Y;
        	if (crane >= 0 && turtle >= 0) {
        		answer = "Yes";
        	}
        }
        
        return answer;
    }
    
    //出力
    public void show(String answer) {
        System.out.println(answer);
    }

}


Measured memory_bytes: 35600
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

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

    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};

int n;
vector<int> to[200005];
mint ans;

int dfs(int v,int p=-1){
    int res=1;
    vector<int> ts;
    for(int u : to[v]){
        if(u==p) continue;
        int t=dfs(u,v);
        res+=t;
        ts.push_back(t);
    }
    if(p!=-1) ts.push_back(n-res);

    mint now=mint(2).pow(n-1)-1;
    for(int t:ts){
        now-=mint(2).pow(t)-1;
    }
    ans+=now;
    return res;
}


int main(){
    cin>>n;
    rep(i,n-1){
        int a,b;
        cin>>a>>b;
        a--,b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    dfs(0);
    ans/=mint(2).pow(n);
    cout<<ans.x<<endl;


}


Measured memory_bytes: 29184
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define rep(i,a,b)  for(ll i=a;i<=b;i++)
using namespace std;

 ll mod=1e9 +7;


const ll M=200006;
ll f[M],inv[M];
ll expo(ll base,ll exponent){
    ll ans=1;
    while(exponent!=0){
        if(exponent&1) ans=(1LL*ans*base)%mod;
        base=(1LL*base*base)%mod;
        exponent>>=1;
    }
    return ans%mod;
}
void compute(){
    f[0]=1;
    rep(i,1,M-1){
        f[i]=(1LL*i*f[i-1])%mod;
    }
    inv[M-1]=expo(f[M-1],mod-2);
    for(ll i=M-2;i>=0;i--){
        inv[i]=(1LL*(i+1)*inv[i+1])%mod;
    }
}
ll C(ll n,ll r){
    return (1LL*((1LL*f[n]*inv[r])%mod)*inv[n-r])%mod;
}

vector<bool>  prime(1000002,true);
void Sieve() 
{ 
   
    for (int p=2; p*p<=1000001; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            for (int i=p*p; i<=1000001; i += p) 
                prime[i] = false; 
        } 
    } 
}

int main()
{

	// #ifndef ONLINE_JUDGE
 //    // for getting input from input.txt
 //    freopen("input.txt", "r", stdin);
 //    // for writing output to output.txt
 //    freopen("output.txt", "w", stdout);
 //    #endif

	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // compute();

    ll tests=1,t=1;
   // cin>>tests;
    while(tests--)
    {
    	int i,ans;
    	vector<int>a(6);
    	for(i=1;i<=5;i++) 
    		{
    			cin>>a[i];
    			if(a[i]==0) ans=i;
    		}
    		cout<<ans;

    }

	return 0;
}

Measured memory_bytes: 3736
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

#define MAX 10000
#define INFTY (1<<20)
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n;
vector<pair<int, int>> adj[MAX];

void dijkstra(){
  priority_queue<pair<int ,int>> PQ;
  int color[MAX];
  int d[MAX];
  for(int i=0; i<n; ++i){
    d[i] = INFTY;
    color[i] = WHITE;
  }

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

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

    if(d[u] < f.first * (-1)) continue;

    for(int j=0; j<adj[u].size(); ++j){
      int v = adj[u][j].first;
      if(color[v] == BLACK) continue;
      if(d[v] > d[u] + adj[u][j].second){
	d[v] = d[u] + adj[u][j].second;
	PQ.push(make_pair(d[v] * (-1), v));
      }
    }
  }

  for(int i=0; i<n; ++i){
    cout << i << " " << ( d[i] == INFTY ? -1 : d[i]) << endl;
  }
  
}


int main(){
  int k, u, v, c;

  cin >> n;
  for(int i=0; i<n; ++i){
    cin >> u >> k;
    for(int j=0; j<k; ++j){
      cin >> v >> c;
      adj[u].push_back(make_pair(v, c));
    }
  }

  dijkstra();



  return 0;
}



Measured memory_bytes: 8052
#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 ordered_set tree<ll, null_type , less<ll> , rb_tree_tag , tree_order_statistics_node_update> 
#define ll long long
#define ull unsigned long long
#define pb push_back
#define inf 1e18
#define mk make_pair
#define ld long double
#define mod 1000000007
#define fi first
#define se second
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test ll t; cin>>t; while(t--)
#define setbits __builtin_popcount
#define endl '\n'
#define LOCAL
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i));}
sim, class b dor(pair < b, c > d) {
    ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
        *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
int main()
{
    ll k;
    cin>>k;
    queue<ll>q;
    for(int i=1;i<=9;i++)
    {
        q.push(i);
    }
    ll x,y,val;
    while(k--)
    {
        x=q.front();
        q.pop();
        if(x%10!=0)
        {
            val=x*10+x%10-1;
            q.push(val);
        }
        val=x*10+x%10;
        q.push(val);
        if(x%10!=9)
        {
            val=x*10+x%10+1;
            q.push(val);
        }
    } 
    cout<<x<<endl;
}

Measured memory_bytes: 1792
#include <stdio.h>

#define N 100

int main(){
  int i,j,k,n,temp,count=0,array[N];
  
  scanf("%d",&n);
  for(i=0; i<n; i++){
    scanf("%d",&array[i]);
  }
  
  for(i=0; i<n; i++){
    for(j=n-1; j>i; j--){
      if(array[j]<array[j-1]){
	temp = array[j];
	array[j] = array[j-1];
	array[j-1] = temp;
	count++;
      }
    }
  }  

  for(i=0; i<n; i++){
    if(i > 0) printf(" ");
    printf("%d",array[i]);
  }
  printf("\n%d\n",count);

  return 0;  
}

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

int main()
{
	string S;
	cin >> S;
	if (S.size() <= 1) {
		puts("YES");
		return 0;
	}
	int cnt[3] = {};
	for (auto c : S) {
		cnt[c - 'a']++;
	}
	sort(cnt, cnt + 3);
	cout << (cnt[2] <= cnt[0] + (S.size() % 3 != 0) ? "YES" : "NO") << endl;
	return 0;
}


Measured memory_bytes: 512
#include <stdio.h>
 
int main(){
  int n, a, b, c, d, i, j, k, h[5][4][11] = {};
  scanf("%d", &n);
  while(n--){
    scanf("%d%d%d%d", &a, &b, &c, &d);
    h[a][b][c] += d;
  }
 
  for(i = 1;i < 5;i++){
    for(j = 1;j < 4;j++){
      for(k = 1;k < 11;k++) printf(" %d", h[i][j][k]);
      puts("");
    }
    if(i != 4){
      for(k = 0;k < 20;k++) putchar('#');
      puts("");
    }
  }
  return 0;
}

Measured memory_bytes: 612
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<string> vs;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;

inline bool valid(int x, int n) {
    return 0 <= x && x < n;
}

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

template <typename T>
inline T pop(queue<T>& q) {
    T front = q.front();
    q.pop();
    return front;
}

template <typename T>
inline T gcd(T a, T b) {
    for (; b; a %= b, swap(a, b));
    return a; 
}

template <typename T>
tuple<T, T, T> xgcd(T a, T b) {
    if (b == 0) return {1, 0, a};
    T x, y, g;
    tie(x, y, g) = xgcd(b, a%b);
    return {y, x-(a/b)*y, g};
}

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

    int N; cin >> N;
    vi A(N); for (int i = 0; i < N; i++) cin >> A[i];
    vll AM, BM;
    for (int i = 0; i < N; i++) {
        AM.push_back(A[i]-i);
        BM.push_back(-A[i]-i);
    }
    sort(AM.begin(), AM.end());
    sort(BM.begin(), BM.end());

    ll rst = 0;
    for (ll am : AM) {
        rst += upper_bound(BM.begin(), BM.end(), am) - lower_bound(BM.begin(), BM.end(), am);
    }

    cout << rst;
}


Measured memory_bytes: 7436
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
typedef long long ll;

ll INF=1e18;
ll v, e, d[105][105], l[105];
bool flag = true;
struct edge { ll from, to, cost; };
edge es[10000];

void warshall_floyd() {
    for (int k = 0; k < v; k++) 
        for (int i = 0; i < v; i++)
            for (int j = 0; j < v; j++) {
                //if (i == 1 && j == 0) cout << d[i][j] << " " << d[i][k] << " " << d[k][j] << endl;
                if (d[i][j] != INF || d[i][k] != INF)
                if (d[i][j] != INF || d[k][j] != INF)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
            
}

bool find_negative_loop() {
    memset(l, 0, sizeof(l));
    for (int i = 0; i < v; i++) {
        for (int j = 0; j < e; j++) {
            edge e = es[j];
            if (l[e.to] > l[e.from] + e.cost) {
                l[e.to] = l[e.from] + e.cost;
                if (i == v - 1) return true;
            }
        }
    }
    return false;
}

int main(void){
    cin >> v >> e;
    
    for (int i = 0; i < v; i++) {
        for (int j = 0; j< v; j++) {
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;
        }
    }
    
    for (int i = 0; i < e; i++) {
        cin >> es[i].from >> es[i].to >> es[i].cost;
        d[es[i].from][es[i].to] = es[i].cost;
    }
    
    warshall_floyd();
    
    if (find_negative_loop()) cout << "NEGATIVE CYCLE" << endl;
    else 
    for (int i = 0; i < v; i++) {
        for (int j = 0; j < v - 1; j++) {
            if (d[i][j] != INF) cout << d[i][j] << " ";
            else cout << "INF ";
        }
        if (d[i][v - 1] != INF) cout << d[i][v - 1];
        else cout << "INF";
        
        cout << endl;
    }
    
}



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

char str[110];
int i,j,k,l,m,n;
int n,e,s,w;
int a[105][7],b[105][7];
int t;

void input() {

  scanf("%d",&n);

  for(j=0;j<n;j++){
  for(i=0;i<6;i++){
    scanf("%d",&a[j][i+1]);
    b[j][i+1] = a[j][i+1];
    // printf("a[%d] = %d\n",i+1,a[i+1]);
  }
  }
}

void N() {
  t = a[m][1];
  a[m][1] = a[m][2];
  a[m][2] = a[m][6];
  a[m][6] = a[m][5];
  a[m][5] = t;
}

void S() {
  t = a[m][1];
  a[m][1] = a[m][5];
  a[m][5] = a[m][6];
  a[m][6] = a[m][2];
  a[m][2] = t;
}

void E() {
  t = a[m][1];
  a[m][1] = a[m][4];
  a[m][4] = a[m][6];
  a[m][6] = a[m][3];
  a[m][3] = t;
}

void W() {
  t = a[m][1];
  a[m][1] = a[m][3];
  a[m][3] = a[m][6];
  a[m][6] = a[m][4];
  a[m][4] = t;
}

void UF() {

  if(a[k][1] == a[m][1]) { // if qu == 1;
    // printf("qu == 1\n");
    if(a[k][2] == a[m][3]) strcpy( str, "NWS");
    else if(a[k][2] == a[m][5]) strcpy(str ,"NEES");
    else if(a[k][2] == a[m][4]) strcpy(str,"NES");


  }  else if(a[k][1] == a[m][2]) {  // if qu == 2;
    // printf("qu == 2\n");
    if(a[k][2] == a[m][3])  strcpy( str, "NWS");
    else if(a[k][2] == a[m][1] ) strcpy(str ,"NEES");
    else if(a[k][2] == a[m][4]) strcpy(str,"NES");
    N();


  } else if(a[k][1] == a[m][3]){ // if qu == 3;
    //   printf("qu(%d) == %d\n",qu[k],a[3]);    
    if(a[k][2] == a[m][6])  strcpy( str, "NWS");
    else if(a[k][2] == a[m][5])  strcpy(str ,"NEES");
    else if(a[k][2] == a[m][1]) strcpy(str,"NES");
    W();


  } else if(a[k][1] == a[m][4]) {
    if(a[k][2] == a[m][1]) strcpy( str, "NWS");
    if(a[k][2] == a[m][5])  strcpy(str ,"NEES");
    if(a[k][2] == a[m][6]) strcpy(str,"NES");
    E();


  } else if(a[k][1] == a[m][5]) {
    if(a[k][2] == a[m][3]) strcpy( str, "NWS");
    else if(a[k][2] == a[m][6])  strcpy(str ,"NEES");
    else if(a[k][2] == a[m][4]) strcpy(str,"NES");
    S();


  } else if(a[k][1] == a[m][6]) {
    if(a[k][2] == a[m][3]) strcpy( str, "NWS");
    else if(a[k][2] == a[m][2])  strcpy(str ,"NEES");
    else if(a[k][2] == a[m][4]) strcpy(str,"NES");
    N();
    N();
  }


}


void output() {

  if(l == 6) printf("No\n");
  else printf("Yes\n");
}

void IF() {

  for(i=0;i<strlen(str);i++) {

    if(str[i] == 'N') N();
    else if(str[i] == 'S') S();
    else if(str[i] == 'W') W();
    else if(str[i] == 'E') E();
  }
}

int main() {


  input();

  for(k=0;k<n;k++) {
    for(m=0; m<n;m++) {

    UF();
    
    IF();

    l=0;

    if(k != m) {
    for(i=1; i<=6;i++) {
      if(a[k][i] == a[m][i]) l++;
      // printf("{a[%d][%d]=%d}  == {a[%d][%d]=%d} ?\n",k,i,a[k][i],m,i,a[m][i]);
    }
    }

    if(l == 6) break;

    }
    if(l ==6) break;
  }

  
    output();



  //  strlen(?) ???????????????(??°)


  return 0;
}

Measured memory_bytes: 584
/// kazuki08
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#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 __gnu_pbds;
using namespace std;
#define int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define ar array
//#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int c[1111],a[111][111];

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
  
  int n,m,x;
  cin >> n >> m >> x;
  for(int i=0;i<n;i++){
    cin >> c[i];
    for(int j=0;j<m;j++){
      cin >> a[i][j];
    }
  }
  int ans = 1e9;
  for(int i=0;i<(1<<n);i++){
    int cnt[m+1]={0};
    int cost = 0;
    for(int j=0;j<n;j++){
      if(i&(1<<j)){
        cost+=c[j];
        for(int k=0;k<m;k++){
          cnt[k]+=a[j][k];
        }
      }
    }
    bool f = true;
    for(int j=0;j<m;j++){
      if(cnt[j]>=x){

      }
      else{
        f = false;
      }
    }
    if(f){
      ans = min(ans,cost);
    }
  }
  if(ans>1e8){
    ans = -1;
  }
  cout << ans << endl;

return 0;
}
///....


Measured memory_bytes: 3680
import Data.List (sort)

adjust::Int->Int->Int->(Int,Int,Int,Int)
adjust a b c | even a && even b && odd c = (a+1,b+1,c,1)
           | even a && odd b && even c = (a+1,b,c+1,1)
           | odd a && even b && even c = (a,b+1,c+1,1)
           | odd a && odd b && even c = (a+1,b+1,c,1)
           | odd a && even b && odd c = (a+1,b,c+1,1)
           | even a && odd b && odd c = (a,b+1,c+1,1)
           | otherwise = (a,b,c,0)
main = do
  [a,b,c] <- map read . words <$> getLine
  let (a',b',c',d) = adjust a b c
  let list = reverse $ sort [a',b',c']
  print $ let m = maximum list in (sum . map (\x -> div (m-x) 2) $ tail list) + d 

Measured memory_bytes: 508
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;

long long N=0,K=0,M=0,A=0,B=0,ans=0,p=0;
long long n=0,s=0,t=0;
string S;
int main(){
    cin >> A >> B >> K;
    if (A <= K){
        s=0;
        t = B - (K-A);
        if(t<0) t=0;
    } else {
        s = A -K;
        t = B;
    }


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


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll sq(ll num) { return num*num; }
ll mod_pow(ll x, ll n) {
	if (n == 0)return 1;
	if (n == 1)return x%MOD;
	ll res = sq(mod_pow(x, n / 2));
	res %= MOD;
	if (n % 2 == 1) {
		res *= x;
		res %= MOD;
	}
	return res;
}

ll k,a,b;

int main(){
	cin >> k >> a >> b;
	if(b-a>2){
		cout << 1 + min(k,a-1) + (max((ll)0,k-(a-1)))/2*(b-a) + (max((ll)0,k-(a-1)))%2 << endl;
	}
	else cout << 1+k << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cctype>
#include <cmath>
#include <iomanip>
#include <climits>
#include <cfloat>
#include <algorithm>
#define ll long long
#define ull unsigned long long
#define uint unsigned
#define MOD 1000000007;
using namespace std;

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

    size_t n {}, k {};
    string s;
    cin >> n >> k >> s;

    s.at(k-1) = tolower(s.at(k-1));
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e5 + 7;
const int Inf = 1 << 30;
const ll INF = 1ll << 60;
int a[5][5];
int n;
int b[15];
bool flg[105];
bool chk;

void Init() {
	for(int i = 1; i <= 3; i++)
		for(int j = 1; j <= 3; j++) scanf("%d", &a[i][j]);
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &b[i]);
		flg[b[i]] = 1;
	}
}

int main() {
	Init();
	for(int i = 1; i <= 3; i++) {
		int cnt = 0;
		for(int j = 1; j <= 3; j++) {
			if(flg[a[i][j]]) cnt++;
		}
		if(cnt == 3) chk = 1;
	}
	for(int i = 1; i <= 3; i++) {
		int cnt = 0;
		for(int j = 1; j <= 3; j++) {
			if(flg[a[j][i]]) cnt++;
		}
		if(cnt == 3) chk = 1;
	}
	if(flg[a[1][1]] && flg[a[2][2]] && flg[a[3][3]]) chk = 1;
	if(flg[a[1][3]] && flg[a[2][2]] && flg[a[3][1]]) chk = 1;
	if(chk) puts("Yes");
	else puts("No");
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

unsigned short a[1000000];

int main(void)
{
	unsigned short s;
	int i,j;
	scanf("%hu",&s);
	a[0] = s;

	for (i=1;i<1000000;i++) {
		if (a[i-1]%2==0) {
			a[i] = a[i-1] / 2;
		} else {
			a[i] = 3*a[i-1] + 1;
		}
		// printf("%hd\n",a[i]);

		for (j=0;j<i;j++) {
			if (a[i] == a[j]) {
				printf("%d\n",i+1);
				return 0;
			}
		}
	}
	
	return 0;
}


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(n);(i)++)
#define repr(i,n) for(int (i)=(n)-1;(i)>=0;(i)--)
#define forin(x,n) for(auto& (x) : n)
#define all(v) (v).begin(),(v).end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define mp make_pair
#define pb push_back
#define MOD 1000000007
#define inf 1000000000
#define llinf 1000000000000000
#define MAX 1000000


typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
typedef vector<pint> vpint;
typedef pair<int,pint> P;

int main(){
    int a,b;
    cin>>a>>b;
    cout<<(int)((a*3+b)/2)<<endl;
}

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

using namespace std;

const long long M = 1e9+7;
long long f[1111111];

long long exp(long long a, long long e) {
    if(e == 1) return a;
    if(e%2) return (a*exp(a,e-1))%M;
    return exp((a*a)%M,e/2);
}

long long inv(long long a) { return exp(a,M-2); }

int main() {
    f[0] = 1;
    for(int i=1;i<1e6;i++) f[i] = (f[i-1]*i)%M;
    int a, b;
    cin >> a >> b;
    int a3 = 2*a-b, b3 = 2*b-a;
    if(a3%3 || b3%3 || a3 < 0 || b3 < 0) cout << 0 << endl;
    else {
        long long r = (f[(a3+b3)/3]*inv(f[a3/3]))%M;
        cout <<  (r*inv(f[b3/3]))%M<< endl;
    }
    return 0;
}


Measured memory_bytes: 8448
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
// dfmt on

void main()
{
    long N = lread();
    auto A = new long[](N);
    foreach (i; 0 .. N)
        A[i] = lread();
    long s = cast(long) sqrt(cast(real) N);
    long d = (N + s - 1) / s;
    auto D = new long[](d);
    D[] = long.min;
    foreach (i; 0 .. N)
    {
        D[i / s] = D[i / s].max(A[i]);
    }
    // writeln(s, D);
    foreach (i; 0 .. N)
    {
        long ans = long.min;
        foreach (j, dv; D)
            if (j != (i / s))
                ans = ans.max(dv);
        foreach (j; (i / s) * s .. min((i / s) * s + s, N))
        {
            if (j != i)
                ans = ans.max(A[j]);
        }
        writeln(ans);
    }
}


Measured memory_bytes: 5628
using System; 
using System.Linq;
using System.Collections.Generic;

class P
{
    static void Main()
    {
        int N = Console.ReadLine().Split().Select(int.Parse).ToArray()[0];
        string[] D = Console.ReadLine().Split();

        int i = N - 1;
        loopHead:;
        i++;
        string iStr = i.ToString();
        foreach (var d in D) if (iStr.Contains(d.ToString())) goto loopHead;
        Console.WriteLine(i);
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
using namespace std;
typedef long long ll;
const int inf = INT_MAX;
const ll INF = 1LL << 60;
const ll mod = 1e9+7;

int main(){
    int n;
    cin >> n;
    vector<vector<ll>> hxy(n, vector<ll>(3));
    rep(i, n) cin >> hxy[i][1] >> hxy[i][2] >> hxy[i][0];
    sort(hxy.begin(), hxy.end(), [](vector<ll> a, vector<ll> b){ return a[0] > b[0];});
    rep(i, 101)rep(j, 101){
      int H = inf;
      rep(k, n){
        if(hxy[k][0] > 0){
          if(k==0){
            H = hxy[k][0] + abs(hxy[k][1]-i) + abs(hxy[k][2]-j);
          }else{
            int tmp = hxy[k][0] + abs(hxy[k][1]-i) + abs(hxy[k][2]-j);
            if(H != tmp){
              H = inf;
              break;
            }
          }
        }else{
            int tmp = abs(hxy[k][1]-i) + abs(hxy[k][2]-j);
            if(H > tmp){
            	H = inf;
                break;
            }
        }
      }
      if(H!=inf){
          cout << i << " " << j << " " << H;
          return 0;
      }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

bool is_month(std::string s) {
    int number = std::stoi(s);
    return (1 <= number && number <= 12);
}

int main() {
    std::string S;
    std::cin >> S;
    bool first_two = is_month(S.substr(0, 2));
    bool last_two = is_month(S.substr(2, 2));
    std::string ans = "NA";
    if (first_two && last_two) {
        ans = "AMBIGUOUS";
    } else if (first_two) {
        ans = "MMYY";
    } else if (last_two) {
        ans = "YYMM";
    }
    std::cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
s=int(input())
a=[s]
for i in range(500):
    if a[i]%2==0:
        a.append(a[i]//2)
    else:
        a.append(a[i]*3+1)
if s==1 or s==2:
    print(4)
else:
    print(a.index(4)+4)

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

int main(){
	int n;
	cin >> n;
	long long num[87];
	num[0] = 2;
	num[1] = 1;
	for(int i = 2;i<=n;i++){
		num[i] = num[i-1]+num[i-2];
		 
	}
	cout << num[n];
	return 0;
}

Measured memory_bytes: 256
(function(input) {
    var l = [];
    for (var i = 'a'.charCodeAt(0); i <= 'z'.charCodeAt(0); i++) {
        l[String.fromCharCode(i)] = 0;
    }

    input.split('').forEach(function(e) {
        e = e.toLowerCase();
        if (e in l) {
            l[e]++;
        }
    });
    console.log(Object.keys(l).map(function(k) {
        return k + ' : ' + this[k];
    }, l).join('\n'));
})(require('fs').readFileSync('/dev/stdin', 'utf8'));

function parse(str, sep, ter) {
    sep = typeof(sep) !== 'undefined' ? sep : ' ';
    ter = typeof(ter) !== 'undefined' ? ter : '\n';
    str = str.replace(/\n$/, '');
    var a = str.split(ter);
    for (var i = 0; i < a.length; i++) {
        a[i] = a[i].split(sep);
    }
    return a;
}

Measured memory_bytes: 8512
#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;
 
using ll = long long;
using ldb = long double;
using pa = pair < ll, ll >;
using vec = vector < ll >;
 
template < typename T > using index_set = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
template < typename T > using MinPriorityQueue = priority_queue < T, vector < T >, greater < T > >;

#define pb push_back
#define po pop_back
#define mp make_pair
#define mt make_tuple
#define F  first
#define S  second
#define f(i,x,n) for(ll i=x;i<n;i++) 
#define all(c) c.begin(),c.end()
#define str string
#define edl "\n"
#define add insert
#define cot continue
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


const int MOD = 1e9 + 7, INF = INT_MAX, N = 1e5 + 10;
const double PI = acos(-1);
const ll LINF = LLONG_MAX;
int main() 
{

  fast();
  
    // #ifndef ONLINE_JUDGE
    //   freopen("input.txt", "r", stdin);
    //   freopen("output.txt","w",stdout);
    // #endif
    ll n;
    cin>>n;
    vec q(n);
    f(i,0,n)
    {
      cin>>q[i];
    }
    ll f=0;
    f(i,1,n)
    {
      if(q[i-1]!=i)
        f++;

    }
    if(f>2)
    {
      cout<<"NO";
    }
    else
    {
      cout<<"YES";
    }









  


    
    cerr << "Time taken: " << int((clock() * 1000.) / CLOCKS_PER_SEC) << "ms\n";
    return 0;
}
 

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

int memo[3005][3005][2], a[3005], b[3005];

int dp(int n, int t, int k) {
	if (n == 0) {
		if ((k && t > 0) || t > a[n])
			return b[n];
		return 0;
	}
	if (memo[n][t][k] != -1) return memo[n][t][k];
	memo[n][t][k] = dp(n - 1, t, k);
	if (k) memo[n][t][k] = max(memo[n][t][k], dp(n - 1, t, 0) + b[n]);
	if (a[n] < t) memo[n][t][k] = max(memo[n][t][k], dp(n - 1, t - a[n], k) + b[n]);
	return memo[n][t][k];
}

int main() {
	int n, t;
	scanf("%d%d", &n, &t);
	for (int i = 0; i < n; i++) scanf("%d%d", &a[i], &b[i]);
	memset(memo, -1, sizeof memo);
	printf("%d\n", dp(n - 1, t, 1));
}


Measured memory_bytes: 71040
#include <iostream>
#include <algorithm>
#include <vector> //動的配列
#include <string>
#include <list> //双方向リスト
#include <map> //連想配列
#include <set> //集合
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <bitset>
#include <numeric>
#include <tuple>




typedef long long ll;


using namespace std;

typedef pair<int, int> P;
#define FOR(i,a,b) for(int i=(int)(a) ; i < (int) (b) ; ++i )
#define rep(i,n) FOR(i,0,n)
#define sz(x) int(x.size())


template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

//小さい順から取り出すヒープ
//priority_queue<ll, vector<ll>, greater<ll> > pque1;
const ll LINF = 1001002003004005006ll;
ll mem[450][450];
vector<ll> a;
int n;

ll dp(int i,int j){
    if (i==j) {
        mem[i][j]=0;
        return 0;
    }
    if (mem[i][j]!=LINF) return mem[i][j];
        
    for (int k=i;k<j;k++){
        mem[i][j]=min(mem[i][j],dp(i,k)+dp(k+1,j)+a[j+1]-a[i]);
    }
    return mem[i][j];
}




int main(){
    cin>>n;
    vector<int> v(n);
    rep(i,n){
        cin>>v[i];
    }
    a.resize(n+1);
    rep(i,n){
        a[i+1]=a[i]+v[i];
        //cout<<a[i]<<endl;
    }
    
    rep(i,n) rep(j,n) mem[i][j]=LINF;
    //dp[i][j]でiからj-1までのスコアの最小
    
   
   dp(0,n-1);
    
    cout<<mem[0][n-1]<<endl;
    
    return 0;
    rep(i,n) {
        rep(j,n) {
            cout<<mem[i][j]<<',';
        } cout<<endl;
    }
    
    
}



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


int main(){
	int m,n,a,sum=0;
	cin >> m >> n;
	for(int i=0;i<n;i++){
		cin >> a;
		sum+=a;
	}
	if(sum>m) cout << -1 << endl;
	else cout << m-sum << endl;
	return 0;
}

Measured memory_bytes: 3612
def point(A, queries):
    ans = 0
    for query in queries:
        a, b, c, d = query
        if A[b - 1] - A[a - 1] == c:
            ans += d
    return ans

def next(A, M):
    for n in range(N):
        if A[N - n - 1] < M:
            A = A[:N - n - 1] + [A[N - n - 1] + 1] * (n + 1)
            return A
    return []



N, M, Q = map(int, input().split())
queries = [[int(i) for i in input().split()] for q in range(Q)]
A = [1] * N
ans = 0
while True:
    ans = max(ans, point(A, queries))
    A = next(A, M)
    if A == []:
        break
print(ans)

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

using namespace std;

int main() {
	int n, c[20], v[20];
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> v[i];
	for (int i = 0; i < n; ++i) cin >> c[i];
	int res = - 1e9 - 7;
	for (int state = 0; state < (1 << n); ++state) {
		int X = 0, Y = 0;
		for (int j = 0; j < n; ++j)
			if (state & (1 << j)) {
				 X += v[j];
				 Y += c[j];
			}				
		res = max(res, X - Y);
	}
	cout << res;
	return 0;
}


Measured memory_bytes: 256
use petgraph::unionfind::UnionFind;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::f64::consts::*;

#[allow(unused)]
const INF: usize = std::usize::MAX / 4;
#[allow(unused)]
const M: usize = 1000000007;

fn main() {
    input! {
        n: usize,
        m: usize,
        ab: [(Usize1, Usize1); m],
    }
    let mut components = UnionFind::new(n);
    for &(ai, bi) in &ab {
        components.union(ai, bi);
    }
    let mut size = HashMap::new();
    for i in 0..n {
        *size.entry(components.find(i)).or_insert(0) += 1usize;
    }
    println!("{}", size.values().max().unwrap());
}


Measured memory_bytes: 10632
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;

void Main() {
  ll a,b,c;
  cin >> a >> b >> c;
  if(a>b) swap(a,b);
  if(a<=c&&c<=b) pr("Yes");
  else pr("No");
}

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


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 10000
#define NIL -1

struct Node{int left, parent, right;};
Node node[MAX];
int n, root;

void preParse(int u){
  if(u == NIL) return;
  cout << " " << u;
  preParse(node[u].left);
  preParse(node[u].right);
}

void inParse(int u){
  if(u == NIL) return;
  inParse(node[u].left);
  cout << " " << u;
  inParse(node[u].right);
}

void postParse(int u){
  if(u == NIL) return;
  postParse(node[u].left);
  postParse(node[u].right);
  cout << " " << u;
}

int main(void){
  cin >> n;

  for(int i = 0; i < n; i++) node[i].parent = node[i].left = node[i].right = NIL;

  for(int i = 0; i < n; i++){
    int id, l, r;
    cin >> id >> l >> r;
    node[id].left = l;
    node[id].right = r;
    if(l != NIL) node[l].parent = id;
    if(r != NIL) node[r].parent = id;
  }

  for(int i = 0; i < n; i++) if(node[i].parent == NIL) root = i;

  cout << "Preorder" << endl;
  preParse(root);
  cout << endl;
  
  cout << "Inorder" << endl;
  inParse(root);
  cout << endl;
  
  cout << "Postorder" << endl;
  postParse(root);
  cout << endl;
  return 0;
}

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

const int MaxM=1e5+5;
const int Mod=1e9+7;

int N,M;
int F[MaxM][3];
bool Tag[MaxM];

struct Matrix{
	int a[3][3];
	
	Matrix(){
		memset(a,0,sizeof(a));
	}
	
	Matrix operator*(Matrix rhs){
		int i,j,k;
		Matrix ans;
		for(i=0;i<3;i++)
			for(j=0;j<3;j++)
				for(k=0;k<3;k++)
					ans.a[i][j]=(ans.a[i][j]+1llu*a[i][k]*rhs.a[k][j])%Mod;
		return ans;
	}
}Trans1,Trans2,Sum;

Matrix Pow(Matrix base,int n){
	Matrix ans;
	ans.a[0][0]=ans.a[1][1]=ans.a[2][2]=1;
	for(;n;n>>=1){
		if(n&1)
			ans=ans*base;
		base=base*base;
	}
	return ans;
}

int main(){
	int i,x,lst=0;
	scanf("%d%d",&N,&M);
	Trans1.a[0][0]=Trans1.a[0][2]=Trans1.a[1][1]=Trans1.a[1][2]=Trans1.a[2][0]=1;
	Trans1.a[0][1]=Trans1.a[2][1]=Trans1.a[2][2]=2;
	Trans2.a[0][0]=Trans2.a[0][2]=Trans2.a[1][1]=Trans2.a[1][2]=Trans2.a[2][2]=1;
	Trans2.a[0][1]=2;
	Sum.a[0][0]=Sum.a[1][1]=Sum.a[2][2]=1;
	while(M--){
		scanf("%d",&x);
		Sum=Sum*Pow(Trans1,x-lst)*Trans2;
		lst=x+1;
	}
	Sum=Sum*Pow(Trans1,N-lst);
	printf("%d\n",Sum.a[0][2]);
	return 0;
}

Measured memory_bytes: 256
H, W = map(int, input().rstrip().split())
a = [list(input()) for _ in range(H)]
a_int = []
for i in range(H):
    tmp = [1 if a[i][j] == "#" else 0 for j in range(W)]
    a_int.append(tmp)
column = []
row = []
for i in range(H):
    if sum(a_int[i])==0:
        row.append(i)
for i in range(W):
    total = 0
    for j in range(H):
        total += a_int[j][i]
    if total == 0:
        column.append(i)
row.reverse()
column.reverse()
for i in row:
    a.pop(i)
for i in column:
    for j in range(len(a)):
        a[j].pop(i)
for S in a:
    print(*S, sep ="")

Measured memory_bytes: 4596