akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N,M;
  cin >> N;
  
  vector<int>T(N);
  for (int i = 0; i < N; i++) {
    cin >> T.at(i);
  }
  cin >> M;
  vector<int>P(M);
  vector<int>X(M);
  for (int i = 0; i < M; i++) {
    cin >> P.at(i) >> X.at(i);
  }
  
  int sum = 0;
  for (int i = 0; i < N; i++) {
    sum += T.at(i);
  }
  
  for (int i = 0; i < M; i++) {
    cout << sum - T.at(P.at(i)-1) + X.at(i) << endl;
  }
}
  
  
  

Measured memory_bytes: 256
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <math.h>
#include <string>
#define ll long long
#define ull unsigned long long
#define make(type,x) type x; cin>>x
#define make2(type,x,y) type x,y; cin>>x>>y
#define fr(x,y) for(long long x=0;x<y;x++)
#define makevec(x,y,n) vector <x> y(n); for(ll i=0;i<n;i++) cin>>y[i]
#define M (ll)1000000007
#define MM (ll) 1e8
#define INF (ll) 1e18

# define IOS ios_base::sync_with_stdio(false); cin.tie(NULL)

using namespace std;

template <typename T>
T modpow(T base, T exp, T modulus) {
  base %= modulus;
  T result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}
bool sortbysec(const pair <ll,ll> &a,const pair <ll,ll> &b){
    return a.second<b.second;
}

struct cmp {
	bool operator() (const pair<int, int> &a, const pair<int, int> &b) const {
		int lena = a.second - a.first + 1;
		int lenb = b.second - b.first + 1;
		if (lena == lenb) return a.first < b.first;
		return lena > lenb;
	}
};


struct c_h {
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        x ^= FIXED_RANDOM;
        return x ^ (x >> 16);
    }
};

ll calcpow(ll x, ll y)
{
    ll temp;
    if(y == 0)
        return 1;
    temp = calcpow(x, y / 2);
    if (y % 2 == 0)
        return temp * temp;
    else
    {
        if(y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b,a%b);

}
ll egcd(ll a, ll b, ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1;
    ll y1;
    ll g=egcd(b,a%b,x1,y1);
    x=y1;
    y=x1-y1*(a/b);
    return g;
}


bool isprime(ll a){
bool flag=1;
for(ll i=2;i*i<=a;i++){
    if(a%i==0) {flag=0; break;}
}
return flag;
}
ll dx[2]={1,0};
ll dy[2]={0,1};

int main(){
    IOS;
    make(ll,n);
    vector <ll> a(n+1);
    fr(i,n) cin>>a[i+1];
    ll i=1;
    vector <ll> vis(n+1);
     bool flag=1; ll ans=0;
    while(true){
        if(i==2) break;
        if(vis[i]==1) {flag=0; break;}
        vis[i]=1; i=a[i]; ans++;
    }
    if(!flag) cout<<"-1 \n";
    else cout<<ans<<endl;
    return 0;
}


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

using namespace std;
#define ll long long int

int main()
{
    int N, K;
    cin >> N >> K;
    int sum = 0;
    int A[N];
    int min = INT_MAX;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
        if (min > A[i])
            min = A[i];
    }
    int i = 0;
    int count = 0;
    while (i < N)
    {
        for (int j = i; j < K + i; j++)
        {   
            if (j > N )break;
            if (A[j] != min)
            {
                count++;
            }
        }
        if (count == K)
        {
            i--;
            sum++;
        }
        else
            sum++;
        //cout << "count = " << count << endl;

        count = 0;

        i += K;
        //cout << "i = " << i << endl;
    }

    /*if (N == K)
    {
        cout << N / K;
        return 0;
    }
    int p = N / K;
    int sum = p + p;
   */
    cout << sum;

    return 0;
}


Measured memory_bytes: 3888
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

MOD = 10**9 + 7

dp = [1 for _ in range(N + 1)]
for A in a:
    dp[A] = 0
for i in range(2, N + 1):
    if dp[i]:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
ans = dp[N]
print(ans)


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif


map<ll, ll> primeFactorize(ll x) {
    map<ll, ll> res;
    res[1] = 1;
    for (ll y = 2; y * y <= x; y++) {
        if (x % y == 0) {
            ll c = 0;
            while (x % y == 0) {
                x /= y;
                c++;
            }
            res[y] = c;
        }
    }
    if (x > 1) res[x] = 1;
    return res;
}

void solve() {
    ll A, B;
    cin >> A >> B;
    ll l = __gcd(A, B);
    auto res = primeFactorize(l);
    cout << res.size()<< '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype

template <class T>
int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define popcount __builtin_popcount

template <class T> void max_swap(T& a, const T b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T b) { a = min(a, b); }

const double EPS = 1e-10;
typedef long long ll;
typedef pair<int, int> pint;


int compress(int* low, int* high, int n, int upper)
{
	vector<int> v;
	for (int i = 0; i < n; ++i)
	{
		v.push_back(low[i]);
		v.push_back(high[i]);
	}
	v.push_back(0);
	v.push_back(upper);

	sort(all(v));
	v.erase(unique(all(v)), v.end());

	for (int i = 0; i < n; ++i)
	{
		low[i] = lower_bound(all(v), low[i]) - v.begin();
		high[i] = lower_bound(all(v), high[i]) - v.begin();
	}

	return v.size() - 1;
}
int main()
{
	int w, h, n;
	while (scanf("%d%d", &w, &h), w | h)
	{
		scanf("%d", &n);
		int x1[1024], x2[1024], y1[1024], y2[1024];
		for (int i = 0; i < n; ++i)
			scanf("%d%d%d%d", x1 + i, y1 + i, x2 + i, y2 + i);

		w = compress(x1, x2, n, w);
		h = compress(y1, y2, n, h);

		static bool painted[2048][2048];
		memset(painted, 0, sizeof(painted));
		for (int i = 0; i < n; ++i)
			for (int y = y1[i]; y < y2[i]; ++y)
				for (int x = x1[i]; x < x2[i]; ++x)
					painted[y][x] = true;

		//for (int y = 0; y < h; ++y)
		//{
		//	for (int x = 0; x < w; ++x)
		//		putchar(painted[y][x] ? '*' : ' ');
		//	puts("|");
		//}

		int res = 0;
		for (int y = 0; y < h; ++y)
		{
			for (int x = 0; x < w; ++x)
			{
				if (!painted[y][x])
				{
					++res;

					static const int dx[] = { 0, 1, 0, -1 };
					static const int dy[] = { 1, 0, -1, 0 };
					queue<pint> q;
					q.push(pint(x, y));
					painted[y][x] = true;
					while (!q.empty())
					{
						pint v = q.front(); q.pop();

						for (int i = 0; i < 4; ++i)
						{
							int tx = v.first + dx[i], ty = v.second + dy[i];
							if (0 <= tx && tx < w && 0 <= ty && ty < h
								&& !painted[ty][tx])
							{
								q.push(pint(tx, ty));
								painted[ty][tx] = true;
							}
						}
					}
				}
			}
		}
		printf("%d\n", res);
	}
}

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

using Lint=long long;

template<int mod> class ModInt
{
 private:
    Lint val;
 public:
    Lint value(){ return val; }
    ModInt(Lint x=0){ val=x%mod; }
    ModInt pow(int n){
        ModInt res(1),x(val);
        while(n>0){ if(n&1) res*=x; x*=x; n>>=1; }
        return res;
    }
    ModInt inv(){ return pow(mod-2); }
    ModInt& operator+=(ModInt rhs){ val+=rhs.val; if(val>=mod) val-=mod; return *this; }
    ModInt& operator-=(ModInt rhs){ val+=mod-rhs.val; if(val>=mod) val-=mod; return *this; }
    ModInt& operator*=(ModInt rhs){ val=val*rhs.val%mod; return *this; }
    ModInt& operator/=(ModInt rhs){ *this*=rhs.inv(); return *this; }
    ModInt operator+(ModInt rhs){ return ModInt(val)+=rhs; }
    ModInt operator-(ModInt rhs){ return ModInt(val)-=rhs; }
    ModInt operator*(ModInt rhs){ return ModInt(val)*=rhs; }
    ModInt operator/(ModInt rhs){ return ModInt(val)/=rhs; }
};
using mint=ModInt<1000000007>;

int main()
{
   int N; cin>>N;
   vector<vector<int>> a(N,vector<int>(N));
   for(int i=0;i<N;i++) for(int j=0;j<N;j++) cin>>a[i][j];

   vector<mint> dp(1<<N);
   dp[0]=1;
   for(int S=0;S<(1<<N)-1;S++){
      int i=__builtin_popcount(S);
      for(int j=0;j<N;j++) if(~S>>j&1 and a[i][j]){
         dp[S|(1<<j)]+=dp[S];
      }
   }
   cout<<dp[(1<<N)-1].value()<<endl;
   return 0;
}


Measured memory_bytes: 16640
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define rep(i,x) for(int i=0;i<x;i++)
typedef complex<double> pt;
typedef pair<pt,pt> L;
typedef vector<P> poly;
const double EPS = 1e-9;
#define x real()
#define y imag()
bool eq(double a,double b){ return -EPS<a-b&&a-b<EPS; }
double dot(pt a,pt b){
	return (conj(a)*b).x;
}
double cross(pt a,pt b){
	return (conj(a)*b).y;
}
bool on_segment(pair<pt,pt> a,pt p){
  return eq(abs(a.first-a.second)-abs(a.first-p)-abs(a.second-p),0);
}
bool contain_point(vector<pt>ps,pt p){
	double sum = 0;
	//arg no sum wo keisan
	for(int i=0;i<ps.size();i++){
		if(on_segment(mp(ps[i],ps[ (i+1)%ps.size() ]),p)) return 1;
		sum += arg( (ps[ (i+1)%ps.size() ]-p) / (ps[i]-p) );
	}
	return (abs(sum) > 1);
}

bool LCMP(const pt& a,const pt& b){
	if(eq(a.x,b.x)) return a.y < b.y;
	else return a.x < b.x;
}
int ccw(pt a,pt b,pt c){
	b -= a; c -= a;
	if(cross(b,c) > EPS) return 1; // counter clockwise
	if(cross(b,c) < -EPS) return -1; // clockwise
	if(dot(b,c) < -EPS) return 2; //c-a-b
	if(norm(b) < norm(c)) return -2; //a-b-c
	return 0; //a-c-b
}
pt crossPoint(pt a,pt b,pt c,pt d){
	double A = cross(b-a,d-c);
	double B = cross(b-a,b-c);
	if( fabs(A) < EPS && fabs(B) < EPS ) return c;
	else if(fabs(A) >= EPS ) return c+B/A*(d-c);
	else pt(1e9,1e9);
}
bool contain_segment(vector<pt>ps,pt p,pt q){
        vector<pt> qs;
      //  if(p == pt(1,2) && q == pt(0,0)) cout << "J" << endl;
        qs.pb(p); qs.pb(q);
    	for(int i=0;i<ps.size();i++){
    		//on-segment
    		if(ccw(p,q,ps[i]) == 0) qs.pb(ps[i]);
    	}
        for(int i=0;i<ps.size();i++){
        	pt r = crossPoint(p,q,ps[i],ps[(i+1)%ps.size()]);
        	if(r.x > 1e8) continue;
        	if(ccw(p,q,r) == 0) qs.pb(r);
        }
        sort(qs.begin(),qs.end(),LCMP);
        for(int i=1;i<qs.size();i++){
            pt r = (qs[i] + qs[i-1]) / 2.0;
            if(!contain_point(ps, r)) return 0;
        }
        return 1;
}
int n;
vector<pt>f;
ll ok[45];
int ans = 40;
void dfs(int v,int num,ll state){
	if(state == (1LL<<n)-1){
		ans = min(ans,num); return;
	}
	if(v == n) return;
	if(ans <= num || num >= 10) return;
	dfs(v+1,num,state);
	dfs(v+1,num+1,state|ok[v]);
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
	    double X,Y;
		scanf("%lf%lf",&X,&Y);
		f.pb(pt(X,Y));
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i==j) ok[i] ^= (1LL<<j);
			else{
				if(contain_segment(f,f[i],f[j])){
					ok[i] ^=  (1LL<<j);
				}
			}
		}
		//cout << ok[i] << endl;
	}//return 0;
	dfs(0,0,0);
	cout << ans << endl;
}

Measured memory_bytes: 3732
#include <stdio.h>
 
int parentNode(int index);
int leftChild(int index);
int rightChild(int index);
 
int nodes[251];
 
main(){
 
    int i, n;
 
    scanf("%d", &n);
 
    for(i=1; i<=n; i++){
        scanf("%d", &nodes[i]);
    }
     
    for(i=1; i<=n; i++){
        printf("node %d: ", i);
        printf("key = %d, ", nodes[i]);
        if(parentNode(i-i%2) > 0)
            printf("parent key = %d, ", nodes[parentNode(i-i%2)]);
        if(leftChild(i) <= n)
            printf("left key = %d, ", nodes[leftChild(i)]);
        if(rightChild(i) <= n)
            printf("right key = %d, ", nodes[rightChild(i)]);
        printf("\n");
    }
     
    return 0;
     
}
 
int parentNode(int i){
    return (int)i/2;
}
 
int leftChild(int i){
    return 2*i;
}
 
int rightChild(int i){
    return 2*i+1;
}

Measured memory_bytes: 0
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	private class Node<T> {
		T value;
		Node<T> left;
		Node<T> right;
		public Node(T value) {
			this.value = value;
			left = right = null;
		}
		public String toString() {
			return value.toString();
		}
	}
	
	public static void main(String[] args) throws IOException {
		new Main().run();
	}
	
	private void run() throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(reader.readLine());
		int[] pre = new int[n];
		int[] in = new int[n];
		StringTokenizer st1 = new StringTokenizer(reader.readLine());
		StringTokenizer st2 = new StringTokenizer(reader.readLine());
		int rootId = 0;
		for (int i = 0; i < n; i++) {
			pre[i] = Integer.parseInt(st1.nextToken());
			in[i] = Integer.parseInt(st2.nextToken());
			if (i == 0) {
				rootId = pre[i];
			}
		}
		reader.close();
		
		Node<Integer> rootNode = new Node<Integer>(rootId);
		for (int i = 1; i < n; i++) {
			Node<Integer> current = new Node<Integer>(pre[i]);
			addNode(rootNode, current, in);
		}
		postOrder(rootNode);
	}

	private void postOrder(Node<Integer> rootNode) {
		StringBuilder sb = new StringBuilder();
		Stack<Node<Integer>> stack = new Stack<Node<Integer>>();
		Node<Integer> current = rootNode;
		Node<Integer> lastVisited = null;
		while (current != null || !stack.isEmpty()) {
			if (current != null) {
				stack.push(current);
				current = current.left;
			} else {
				Node<Integer> peekNode = stack.peek();
				if (peekNode.right != null && peekNode.right != lastVisited) {
					current = peekNode.right;
				} else {
					if (sb.length() == 0) {
						sb.append(peekNode);
					} else {
						sb.append(" " + peekNode);
					}
					lastVisited = stack.pop();
				}
			}			
		}
		System.out.println(sb.toString());
	}

	private void addNode(Node<Integer> rootNode, Node<Integer> newNode, int[] in) {
		int pos1 = findPos(in, newNode.value);
		Stack<Node<Integer>> stack = new Stack<Node<Integer>>();
		stack.push(rootNode);
		while (!stack.isEmpty()) {			
			Node<Integer> current = stack.pop();
			int pos2 = findPos(in, current.value);
			if (pos1 < pos2) {
				if (current.left == null) {
					current.left = newNode;
					return;
				} else {
					stack.push(current.left);
				}
			} else {
				if (current.right == null) {
					current.right = newNode;
					return;
				} else {
					stack.push(current.right);
				}
			}
		}
	}

	private int findPos(int[] in, int id) {
		for (int i = 0; i < in.length; i++) {
			if (in[i] == id) {
				return i;
			}
		}
		return -1;
	}
}



Measured memory_bytes: 24332
import java.util.Scanner;

import static java.lang.Math.max;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int[][] gain = new int[n][3];

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

            String[] abc = sc.nextLine().split(" ");
            gain[i][0] = Integer.parseInt(abc[0]);
            gain[i][1] = Integer.parseInt(abc[1]);
            gain[i][2] = Integer.parseInt(abc[2]);
        }

        // dp[i][j] := j - 1番目でiを選んだときの最適解
        int[][] dp = new int[n + 1][3];

        dp[0][0] = 0;
        dp[0][1] = 0;
        dp[0][2] = 0;

        for (int j = 1; j <= n; j++) {
            dp[j][0] = max(dp[j - 1][1], dp[j - 1][2]) + gain[j - 1][0];
            dp[j][1] = max(dp[j - 1][2], dp[j - 1][0]) + gain[j - 1][1];
            dp[j][2] = max(dp[j - 1][0], dp[j - 1][1]) + gain[j - 1][2];
        }

        System.out.println(max(max(dp[n][0], dp[n][1]), dp[n][2]));

    }
}

Measured memory_bytes: 132816
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const int MOD = 998244353;
const ll INF = 1000000000000000000;

int A[21], B[21], C[21];
int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)  cin >> A[i];
	for (int i = 0; i < N; i++)  cin >> B[i];
	for (int i = 0; i < N - 1; i++)  cin >> C[i];
	int ans = 0;
	for (int i = 0; i < N; i++) {
		ans += B[i];
		if (A[i] == A[i + 1] - 1)  ans += C[A[i] - 1];
	}
	cout << ans << endl;
}

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

int f(int m, int a) {
	return m % a;
}

int main() {
	string s; cin >> s;
	long long k; cin >> k;
	int one = 0;
	for (int i = 0; i < s.size(); i++)
	{
		if(s[i] != '1') break;
		one++;
	}
	if(one == s.size()) cout << "1" << endl;
	else if(one >= k) cout << "1" << endl;
	else cout << s[one] << endl;
	return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int> smin;
  {
    deque<int> d;
    for (int i = 0; i < n; i++) {
      while (d.size() && a[d.back()] > a[i]) d.pop_back();
      d.push_back(i);
      if (i >= k - 1) smin.push_back(a[d[0]]);
      if (d[0] <= i - k + 1) d.pop_front();
    }
  }
  vector<int> smax;
  {
    deque<int> d;
    for (int i = 0; i < n; i++) {
      while (d.size() && a[d.back()] < a[i]) d.pop_back();
      d.push_back(i);
      if (i >= k - 1) smax.push_back(a[d[0]]);
      if (d[0] <= i - k + 1) d.pop_front();
    }
  }
  vector<int> bad(n - 1);
  for (int i = 0; i < n; i++) {
    if (a[i] > a[i + 1]) bad[i]++;
  }
  vector<int> pref(n);
  for (int i = 0; i + 1 < n; i++) {
    pref[i + 1] = pref[i] + bad[i];
  }
  int ans = 0;
  int nosort = 0;
  for (int i = 0; i <= n - k; i++) {
    if (pref[i + k - 1] == pref[i]) {
      nosort = 1;
      continue;
    }
    if (i > 0 && smin[i - 1] == a[i - 1] && smax[i] == a[i + k - 1]) continue;
    ans++;
  }
  cout << ans + nosort << '\n';
  return 0;
}

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

int main(){
  ull n,i,j,c=0,sum=0;
  cin>>n;
  ull a[n];
  for(i=0;i<n;i++){
     cin>>a[i];
  }
  for(i=0;i<n;i++){
     for(j=0;j<=i;j++){
        if(a[i]>=a[j])
            c++;
     }
     if(c==i+1)
        sum++;

     c = 0;
  }
  cout<<sum<<endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector> 
#include<cstring>
using namespace std;
const int maxn = 1e5 + 5;
vector<int> list[maxn];
int vis[maxn];
int lose=0;
void bfs(int ne,int be,int re)
{
    if(!lose)
    {
        if(vis[ne]==-1)
            vis[ne]=re;
        else
            if(vis[ne]!=re)
            {
                lose=1;
                return;
            }
            else
                return;
        for(int i=0;i<list[ne].size();i++)
        {
            if(list[ne][i]!=be)
                bfs(list[ne][i],ne,!re);    
        }

    }

}
int main()
{
    long long m,n;
    scanf("%lld%lld",&m,&n);
    for(int i=0;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        list[x].push_back(y);
        list[y].push_back(x);
    }
    memset(vis,-1,sizeof(vis));
    bfs(1,0,1);
    long long q=0,p=0;
    for(int i=1;i<=m;i++)
    {
        if(vis[i]==1)
            q++;
        else
            p++;
    }
    if(lose)
        printf("%lld\n",m*(m-1)/2-n);
    else
        printf("%lld\n",q*p-n);

    return 0;
}

Measured memory_bytes: 6656
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
r = n
ans = 0
for i in range(n):
    if i>=r:
        ans += 1
        r = n
    if not graph[i]:
        continue
    mi = min(graph[i])
    r = min(r, mi)
print(ans)

Measured memory_bytes: 17968
import bisect
n,k=map(int,input().split())
x=list(map(int,input().split()))
y=[0]*n
for i in range(n):
    y[i]=-x[n-1-i]
#print(y)

if x[0]>=0:print(x[k-1])
elif x[-1]<=0:print(abs(x[n-k]))
else:
    c=bisect.bisect_left(x,0)
    d=bisect.bisect_right(x,0)
    ans=float('inf')
    if c+k-1<=n-1:
        ans=abs(x[c+k-1])
    if d-k>=0:
        ans=min(ans,abs(x[d-k]))
    for i in range(n-1,c-1,-1):
        if i-k+1>=0:
            ans1=x[i]+2*abs(x[i-k+1])
        #print(ans1)
        if ans1<ans:
            ans=ans1
    #print(ans)
if y[0]<0 and y[-1]>0:
    c=bisect.bisect_left(y,0)
    d=bisect.bisect_right(y,0)
    Ans=float('inf')
    if c+k-1<=n-1:
        Ans=abs(y[c+k-1])
    if d-k>=0:
        Ans=min(Ans,abs(y[d-k]))
    for i in range(n-1,c-1,-1):
        if i-k+1>=0:
            Ans1=y[i]+2*abs(y[i-k+1])
        #print(Ans1)
        if Ans1<Ans:
            Ans=Ans1
    #print(ans,Ans)
    print(min(Ans,ans))

Measured memory_bytes: 62576
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(20000)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f

def main():
	MOD = 10**9 + 7
	n = int(rl())
	A = []
	for _ in range(n):
		row = []
		for bit in rli():
			row.append(bit)
		A.append(row)

	dp = [0 for _ in range(1 << n)]
	dp[0] = 1
	for mask in range((1 << n)-1):
		new = popcount(mask)
		for cand in range(n):
			if A[new][cand] and not (mask & (1 << cand)):
				nmask = mask ^ (1 << cand)
				dp[nmask] += (dp[mask] % MOD)
				dp[nmask] %= MOD
	print(dp[-1]) 
	stdout.close()

if __name__ == "__main__":
	main()

Measured memory_bytes: 207900
#include <cstdio>
#include <algorithm>

typedef long long i64;

const int N = 100000 + 10;

int n, a[N];
i64 sum[N], pre[N], suf[N];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  int ans = 0;
  std::sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i];
  // a_i <= 2 * (sum[i - 1] + x)
  for (int i = 1; i <= n; ++i) pre[i] = std::max(pre[i - 1], a[i] - 2 * sum[i - 1]);
  for (int i = n; i > 0; --i) suf[i] = std::max(suf[i + 1], a[i] - 2 * sum[i - 1]);
  for (int i = 1; i <= n; ++i)
    if (pre[i - 1] <= 2LL * a[i] && suf[i + 1] <= 0) ++ans;
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 2944
#include <stdio.h>
int main(void)
{
    char s[11];
    int i=0, cnt=0, j=0, max=0;
    scanf("%s", s);

    while(s[i]!='\0'){
        cnt=0;
        j=i;
        while(s[j]!=0){
            if(s[j]=='A' || s[j]=='C' || s[j]=='G' || s[j]=='T'){
                cnt++;
                j++;
            }
            else{
                j=0;
                break;
            }
        }
        if(cnt>max) max=cnt;
        i++;
    }

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

    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <map>

typedef long long ll;
#define fi first
#define se second

using namespace std;

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

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

int n;
int m;
int x[112345];
int y[112345];
ll dx;
ll dy;
ll mod = 1000000007;
        //123456789
ll num;


ll ans;

int main(){
  
  int i;
  int j;
  ll c;
  ll d;
  
  cin>>n>>m;
  
  for( i = 0; i < n; i++ ){
    scanf("%d", x+i );
  }
  
  for( i = 0; i < m; i++ ){
    scanf("%d", y+i );
  }
  
  dx = 0;
  dy = 0;
  
  for( i = 1; i < n; i++ ){
    c = (ll)i*((ll)n-(ll)i);
    c %= mod;
    d = (ll)x[i] - (ll)x[i-1];
    d %= mod;
    dx += c * d;
    dx %= mod;    
  }
  
  for( i = 1; i < m; i++ ){
    c = (ll)i*((ll)m-(ll)i);
    c %= mod;
    d = (ll)y[i] - (ll)y[i-1];
    d %= mod;
    dy += c * d;
    dy %= mod;
  }
  
  ans = dx * dy;
  ans %= mod;
  
  cout<<ans<<endl;
  
  return 0;
}

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

typedef long long ll;

ll x,y;

int main(void){
    cin>>x>>y;
    ll z=max(x, y)-min(x, y);
    if(z<2){
        cout<<"Brown"<<endl;
    }else{
        cout<<"Alice"<<endl;
    }
    return 0;
}


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

using namespace std;

#define all(c) (c).begin(), (c).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

int main() {
    int N, M;
    cin >> N;
    vector<int> T(N);
    rep(i, N) cin >> T[i];
    cin >> M;
    vector<int> P(M), X(M);
    rep(i, M) cin >> P[i] >> X[i];
    rep(i, M) P[i]--;
    long long sum = 0;
    rep(i, N) sum += T[i];
    rep(i, M) {
        cout << sum + X[i] - T[P[i]] << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[1000000]={0};
int main()
{
    int b,c,d,e,f,i,j,k,l;
    cin>>b;
    for(i=0;i<b-1;i++)
    {
        cin>>c;
        a[c]++;
    }
    for(j=1;j<=b;j++)
    {
        printf("%d\n",a[j]);
    }
    return 0;
}


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

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e5;
char s[MAXN + 5];
int l, r, f[MAXN + 5];
bool flag;

int main() {
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	for (int pos, i = 1; i <= n; ) {
		if (s[i] == 'R') ++r, ++i;
		else {
			pos = i;
			for (; i <= n && s[i] == 'L'; ++i) ++l;
			if ((l + r) & 1) {
				if ((l & 1) && !(r & 1)) f[pos - 1] = (l + r) / 2, f[pos] = (l + r) / 2 + 1;
				else f[pos - 1] = (l + r) / 2 + 1, f[pos] = (l + r) / 2;
			} else f[pos - 1] = f[pos] = (l + r) / 2;
			l = r = 0;
		}
	}
	for (int i = 1; i <= n; ++i) {
		write(f[i]);
		putchar(' ');
	}
	putchar('\n');
	return 0;
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

typedef long long ll;
typedef long double R;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

// Problem Specific Parameter:

int main() {
  string s; cin >> s;
  string ans="";
  for(int i = 0; i < s.length()-8; i++) {
    ans.push_back(s[i]);
  }
  cout << ans << endl;

  return 0;
}

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


public class Main {

    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner(System.in);
	String[] a=sc.nextLine().split(" ");
	int H=Integer.parseInt(a[0]);
	int N=Integer.parseInt(a[1]);
	String[] line=sc.nextLine().split(" ");
	int[] A=new int[N];
	for(int i=0;i<N;i++){
	A[i]=Integer.parseInt(line[i]);
	}
	Arrays.sort(A);
	int flag=0;
	for(int i=0;i<N;i++){
	H-=A[N-i-1];
	if(H<=0)flag=1;
	}
	if(flag==1)
	System.out.println("Yes");
	else
	System.out.println("No");
		
	
    }

    static class FastScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        public String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return tokenizer.nextToken("\n");
        }

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

        public long nextInt() {
            return Integer.parseInt(next());
        }

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



        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        } 
    }
}


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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  long N, K;
  cin >> N >> K;
  vector<long> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  sort(A.begin(), A.end());
  long ok = -2e18, ng = 2e18;
  while (ng - ok > 1) {
    long mid = (ok + ng) / 2, sum = 0;
    for (int i = 0; i < N; i++) {
      if (A.at(i) > 0) sum += lower_bound(A.begin(), A.end(), (long double) mid / A.at(i)) - A.begin();
      if (A.at(i) < 0) sum += N - (upper_bound(A.begin(), A.end(), (long double) mid / A.at(i)) - A.begin());
      if (A.at(i) == 0) sum += (mid > 0) ? N : 0;
      if (A.at(i) * A.at(i) < mid) sum--;
    }
    (sum / 2 < K) ? ok = mid : ng = mid;
  }
  cout << ok << "\n";
}


Measured memory_bytes: 4780
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int mod = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0 , -1};
signed main() {
    string S = "keyence";
    string T;
    cin >> T;
    for(int i = 0; i <= 7; i++) {
        if(T.substr(0,i)+T.substr(T.size()-7+i) == S) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
 
using namespace std;
inline void prep ()
{
  cin.tie (0);
  cin.sync_with_stdio (0);
};
const double pi = acos(-1.);
//printf(%.12lf\n,mid);
// __builtin_popcount(int) count 1's in binary
// get decimal part of number
/*
double intpart;
double thiss = modf((double)(n*m)/(double)k, &intpart);
*/
// round = (int)(num+.5)
long long mod = 1000000007;

// 32 mil = ~1 sec 
long long mymod(long long num){
  if (num< 0 && !(num%mod == 0)){
    if (mod == 1){
      return 0;
    }
    return mod-abs(num)%mod;
  }else{
    return num%mod;
  }
}
 
/*string sentence = And I feel fine...;
    istringstream iss(sentence);
*/  
 
double eps = .000000001;

int main ()
{
  prep();
  int n;
  cin >> n;
  long long cur = 0;
  long long lasta = 1; 
  long long lastb = 1;
  for (int i=0; i<n; i++){
      long long a, b;
      cin >> a >> b;
      long long tot = a+b;
      long long diva = lasta/a+(lasta%a != 0);
      long long divb = lastb/b+(lastb%b != 0);
      //cout << lasta << " " << lastb << " " << diva << " " << divb << endl;
      long long maxx = max(diva, divb);
      lasta = maxx*a;
      lastb = maxx*b;
  }
  cout << lasta+lastb;
  return 0; 
}


Measured memory_bytes: 256
void main() {
	auto N = ri;
	auto S = rs;
	if(S.length == 1) {
		writeln(3);
		return;
	}
	bool[] arr;
	ulong index = 0;
	while(index < N - 1) {
		if(S[index] != S[index+1]) {
			arr ~= false;
			if(index == N - 2) arr ~= false;
			index++;
		} else {
			arr ~= true;
			index += 2;
		}	
	}
	ulong res;
	if(arr[0]) res = 6;
	else res = 3;
	const ulong MOD = 1000000007;
	alias Pair = Tuple!(bool, "a", bool, "b");
	foreach(k; 0..arr.length-1) {
		auto t = arr[k], i = arr[k+1];
		if([t, i] == [false, false] || [t, i] == [false, true])
			res = (res * 2) % MOD;
		if([t, i] == [true, true])
			res = (res * 3) % MOD;
		t = i;
	}
	res.writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}


Measured memory_bytes: 380
/*   _ _ _                     
    | | | | ___  ___           
    | | | || . ||  _|          
    |_____||_  ||_|  _____     
             |_|    |_____|  */
// Time : 19/10/16
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
int main(){
#ifdef Wqr_
    freopen("in.txt","r",stdin);
#endif
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    ll a, b;
    cin >> a >> b;
    ll c = __gcd(a, b);
    ll d = c, ans = 1;
    for(ll i = 2; i * i <= c; i++){
        if(c % i == 0){
            ans++;
            while(c % i == 0) c /= i;
        }
    }
    if(c != 1) ans++;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import itertools
n,c = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(c)]
C = [list(map(int,input().split())) for _ in range(n)]
mod0 = []
mod1 = []
mod2 = []
for i in range(n):
    for j in range(n):
        # indexのずれを考慮 ((i+1)+(j+1))%3が本来のmod値
        if (i+j)%3 == 1:
            mod0.append(C[i][j]-1)
        elif (i+j)%3 == 2:
            mod1.append(C[i][j]-1)
        else:
            mod2.append(C[i][j]-1)

conv_0, conv_1, conv_2 = [],[],[]
for i in range(c):
    tmp0, tmp1, tmp2 = 0,0,0
    for j in range(len(mod0)):
        tmp0 += D[mod0[j]][i]
    for j in range(len(mod1)):
        tmp1 += D[mod1[j]][i]
    for j in range(len(mod2)):
        tmp2 += D[mod2[j]][i]
    conv_0.append(tmp0)
    conv_1.append(tmp1)
    conv_2.append(tmp2)
res = float('inf')
color_range = list(range(c))
for x,y,z in itertools.permutations(color_range, 3):
    cnt = 0
    cnt = conv_0[x] + conv_1[y] + conv_2[z]
    res = min(cnt, res)
print(res)

Measured memory_bytes: 56796
#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() {
  int d,t,s;
  cin >> d >> t >>s;
  if (d>t*s) cout << "No"<< endl;
  else cout << "Yes" <<endl;
 
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int X;
int main(){
	cin >> X; int t = 7%X;
	int ans;
	for(ans = 1;t;++ans,t = (t*10+7)%X)
		if(ans >= 10000000)	return puts("-1"),0;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3740
#include <stdio.h>

int main(void)
{
    int a, b, c, sum = 0;
    scanf("%d %d %d", &a, &b, &c);
    while(a <= b){
        if((c % a) == 0) sum ++;
        a++;
    }
    printf("%d\n", sum);
    return (0);
}


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

int N,A,B,C; 
int l[8];
int ans = 1e9;
void dfs(int a, int b, int c, int cur, int mp){
    if(cur == N){
        if(min(a,min(b,c)) > 0) ans = min(ans,abs(a-A) + abs(b-B) + abs(c-C) + mp -30);
        return; // A,B,Cすべてに1つ以上竹を使っているとき値の更新
    }
    dfs(a,b,c,cur+1,mp); // cur番目の竹を使わない
    dfs(a+l[cur],b,c,cur+1,mp+10); // cur番目の竹をAの材料に使う
    dfs(a,b+l[cur],c,cur+1,mp+10); // cur番目の竹をBの材料に使う
    dfs(a,b,c+l[cur],cur+1,mp+10); // cur番目の竹をCの材料に使う
    return;
}

int main(){
    cin >> N >> A >> B >> C;

    for (int i = 0; i < N; i++)
    {
        cin >> l[i];
    }
    dfs(0,0,0,0,0);

    cout << ans << endl;
}

Measured memory_bytes: 256
using System;
class some
{
	public static void Main()
	{
		string[]ss=Console.ReadLine().Split();
		int a=int.Parse(ss[0]);
		int b=int.Parse(ss[1]);
		if(a>8 || b>8)Console.WriteLine(":(");
		else Console.WriteLine("Yay!");
	}
}


Measured memory_bytes: 13140
#[allow(unused_imports)]
use proconio::{fastout, input};

#[fastout]
fn main() {
    input!(n: usize);
    for i in 1..10 {
        for j in 1..10 {
            if n == i * j {
                println!("{}", "Yes");
                return;
            }
        }
    }
    println!("{}", "No");
}


Measured memory_bytes: 2164
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);

		String input = sc.nextLine();
		
		for(char c : input.toCharArray()){
			System.out.print(('a' <= c && c <= 'z' || 'A' <= c && c <= 'Z') ? (char) (c ^ ('a' - 'A'))  : c);
		}
		System.out.println();
	}

}

Measured memory_bytes: 17244
#define ENABLE_DEBUG 1
// Kana's kitchen {{{
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
#define LOOP(k) for(i64 ngtkana_is_a_genius=0; ngtkana_is_a_genius<(i64)k; ngtkana_is_a_genius++)

using i32 = std::int_least32_t;
using i64 = std::int_least64_t;
using u32 = std::uint_least32_t;
using u64 = std::uint_least64_t;
using usize = std::size_t;

template <class T> using vec = std::vector<T>;
template <class T> using numr = std::numeric_limits<T>;

#ifdef NGTKANA
#include<debug.hpp>
#else
#define DEBUG(...)(void)0
#endif
/*}}}*/
int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(15) << std::fixed;

    usize n;
    std::cin >> n;
    vec<i64> x(n), len(n);
    for (usize i=0; i<n; i++) {
        std::cin >> x.at(i) >> len.at(i);
        len.at(i) -= x.at(i);
    }

    std::priority_queue<i64, vec<i64>, std::less<>> pl;
    std::priority_queue<i64, vec<i64>, std::greater<>> pr;
    vec<i64> ml(n), mr(n);
    i64 gl=0, gr=0;
    ml.at(0) = x.at(0);
    mr.at(0) = x.at(0);
    pl.push(x.at(0));
    pr.push(x.at(0));
    for (usize i=1; i<n; i++) {
        assert(pl.top()-gl <= pr.top()+gr);
        gl += len.at(i);
        gr += len.at(i-1);
        pl.push(x.at(i) + gl);
        pr.push(x.at(i) - gr);
        pl.push(pr.top()+gr+gl); pr.pop();
        pr.push(pl.top()-gr-gl); pl.pop();
        ml.at(i) = pl.top()-gl;
        mr.at(i) = pr.top()+gr;
    }

    vec<i64> pos(n);
    pos.at(n-1) = ml.at(n-1);
    for (usize i=n-2; i!=-1; i--) {
        i64 l = pos.at(i+1) - len.at(i);
        i64 r = pos.at(i+1) + len.at(i+1);
        pos.at(i) = r < ml.at(i)
            ? r
            : mr.at(i) < l
            ? l
            : ml.at(i)
            ;
    }

    i64 ans = 0;
    for (usize i=0; i<n; i++) {
        ans += std::abs(pos.at(i) - x.at(i));
    }
    std::cout << ans << '\n';
}


Measured memory_bytes: 5996
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin,(a).rend()
#define dunk(a) cout << (a) << endl
using namespace std;
typedef long long ll;
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n;
	cin >> n;
	map<ll, ll> mp;
	for (int i = 1; i <= n; ++i) {
		mp[i]++;
	}
	for (int i = 2; i <= n; ++i) {
		int a = i;
		for (int j = 2; j <= n; ++j) {
			while (a % j == 0) {
				mp[j]++;
				a /= j;
			}
			if (a == 1) break;
		}
	}
	ll ans = 1;
	for (auto& c : mp) {
		ans = ans * c.second % mod;
	}
	ans = (ans % mod + mod) % mod;

	dunk(ans);

	return 0;
}

Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main()
{
    int a,b,temp;
    while(cin>>a>>b)
    {
        temp=0;
        if(a>=10)
        {
            cout<<b<<endl;
        }
        else if(a<10)
        {
            temp=(100)*(10-a);
            cout<<temp+b<<endl;
        }
    }
}

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

#define N 100

int n;
int d[N];

int main()
{
	int ans = 1;

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

	sort( d, d + n );
	for( int i = 1; i < n; i++ ) {
		if( d[i] > d[i - 1] ) {
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
// In the name of Allah the Lord of the Worlds.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

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

    int n;
    cin >> n;
    vector<int>v(n);
    for(auto &x:v)cin >> x;
    int now = 0 , ans = 0;
    reverse(v.begin() , v.end());
    for(int i=1;i<v.size();i++){
        if(v[i]>=v[i-1]){
            now++;
            ans = max(ans , now);
        }
        else{
            now = 0;
        }
    }
    cout << ans << endl;

    return 0;
}


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

int main() {
    int N; cin >> N;
    vector<P> ab(N);
    rep(i, N) {
        int x, y;
        cin >> x >> y;
        ab[i] = P {x, y};
    }
    vector<P> cd(N);
    rep(i, N) {
        int x, y;
        cin >> x >> y;
        cd[i] = P {x, y};
    }

    sort(ab.begin(), ab.end());
    sort(cd.begin(), cd.end());

    int abi = N-1;
    int ans = 0;
    /*
    cout << "Coutn" << endl;
    for (int i=N-1; i>=0; --i) {
        cout << "cd: " << cd[i].first << " " << cd[i].second << endl;
        // c = cd[i].first;
        // d = cd[i].second;
        for (int j=ab.size()-1; j>=0; --j) {
            if (cd[i].first > ab[j].first && cd[i].second > ab[j].second) {
                cout << "ab: " << ab[j].first << " " << ab[j].second << endl;
                ans += 1;
                // abi = j-1;
                break;
            }
        }
    }*/
    rep(i, N) {
        P match_i = {0, -1};
        int temp_j = N;
        // cout << "cd: " << cd[i].first << " " << cd[i].second << endl;
        // rep(j, ab.size()) cout << ab[j].first << " " << ab[j].second << endl;
        rep(j, ab.size()) {
            if (cd[i].first > ab[j].first && cd[i].second > ab[j].second && ab[j].second > match_i.second) {
                match_i = ab[j];
                temp_j = j;
            }
        }
        if (temp_j != N) {
            // cout << "ab: " << match_i.first << " " << match_i.second << endl;
            ab.erase(ab.begin()+temp_j);
            ans += 1;
        }
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
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; }
 
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define INF 10000000000
#define MOD 1000000007
using ll = long long;
using pint = pair<int,int>;
using pll = pair<ll,ll>;
using Graph = vector<vector<int>>;

int main(){
    int N,C; cin>>N>>C;
    vector<vector<ll>> D(C+1,vector<ll>(C+1,0));
    rep(i,C)rep(j,C)cin>>D[i+1][j+1];
    vector<map<int,ll>> V(3);
    vector<vector<ll>> c(N,vector<ll>(N,0));
    rep(i,N)rep(j,N){
        cin>>c[i][j];
        V[(i+j)%3][c[i][j]]++;
    }
    ll res = -1;
    rep1(i,C){
        rep1(j,C){
            rep1(k,C){
                if(i==j||j==k||k==i)continue;
                ll tmp = 0;
                for(auto p:V[0]){
                    //turn i;
                    int color = p.first;
                    int cnt = p.second;
                    tmp += D[color][i]*cnt;
                }
                for(auto p:V[1]){
                    //turn j;
                    int color = p.first;
                    int cnt = p.second;
                    tmp += D[color][j]*cnt;
                }
                for(auto p:V[2]){
                    //turn k;
                    int color = p.first;
                    int cnt = p.second;
                    tmp += D[color][k]*cnt;
                }
                if(res==-1)res = tmp;
                else res = min(res,tmp);
            }
        }
    }
    cout<<res<<endl;
}


Measured memory_bytes: 5608
#define _USE_MAT_DEFINES
#include<iostream>
#include <iomanip>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <deque>
#include <numeric>
#include <functional>
using namespace std;

long long cost(int x, int y) {
    return (x - y)*(x - y);
}

int main() {
    int N, min_ = 100, max_ = -100;
    cin >> N;
    vector<int>a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        min_ = min(min_, a[i]);
        max_ = max(max_, a[i]);
    }

    long long ans = 1e9;
    for (int i = min_; i <= max_; i++) {
        long long c = 0;
        for (int j = 0; j < N; j++) {
            c += cost(a[j], i);
        }
        ans = min(ans, c);
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair < int, int >;

ll lcm (ll a, int b) {
	int g = __gcd ((int) a, b);
	ll l = a * b;
	l /= g;
	return l;
}

int main() {
	ios::sync_with_stdio (false);
	int n, m;
	cin >> n >> m;
	vector < int > a (n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int & x : a) x >>= 1;
	ll l = 1;
	for (int i = 0; i < n; i++) {
		l = lcm (l, a[i]);
		if (l > m) {
			cout << 0 << endl;
			return 0;
		}
	}
	bool possible = true;
	for (int x : a) {
		if ((l / x) % 2 == 0) {
			possible = false;
			break;
		}
	}
	if (!possible) {
		cout << 0 << endl;
		return 0;
	}
	n = m / l;
	n = (n + 1) / 2;
	cout << n << endl;
	return 0;
}



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

int main(void)
{
    int n;
    cin >> n;
    int a[n+1], b[n+1], c[n];

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

    int out = b[a[1]];

    for(i=2;i<n+1;i++)
    {
        out += b[a[i]];
        if(a[i] == a[i-1] + 1)
        {
            out += c[a[i] -1];
        }
    }

    cout << out << endl;

    return 0;
}

Measured memory_bytes: 256