akhauriyash/Code-Regression huggingface dataset:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

class Graph():
    def __init__(self, v):
        from heapq import heappop, heappush
        self.v = v
        self.graph = [[] for _ in range(v)]
        self.INF = 10 ** 9
    
    def addEdge(self, start, end, itr):
        self.graph[start].append((end, itr))
        self.graph[end].append((start, itr))
    
    def BFS(self, start):
        from collections import deque
        dist = [-1] * self.v
        ret = [0] * (self.v-1)
        que = deque()
        que.append((start, -1))
        dist[start] = 0
        while que:
            now, _color = que.popleft()
            color = 1
            if _color == color: color += 1
            for to, itr in self.graph[now]:
                if dist[to] == -1:
                    que.append((to, color))
                    dist[to] = dist[now] + 1
                    ret[itr] = color
                    color += 1
                    if color == _color: color += 1
        return ret
    
    def color_types(self):
        ret = len(self.graph[0])
        for x in self.graph[1:]:
            ret = max(ret, len(x))
        return ret

def Main():
    n = read_int()
    g = Graph(n)
    for i in range(n - 1):
        a, b = read_ints()
        g.addEdge(~-a, ~-b, i)
    print(g.color_types())
    print(*g.BFS(0), sep='\n')

if __name__ == '__main__':
    Main()

Measured memory_bytes: 45172
#include<bits/stdc++.h>
#define MOD 1000000007
#define MOD2 1000000006
#define TEMPMOD1 998244353
#define TEMPMOD2 998244352
#define INF 1000000000000000007
#define NEGINF -1000000000000000007
#define vll vector<ll> 
#define vvll vector<vector<ll>>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define plll pair<ll,pll>
#define vpll vector<pll>
using namespace std;
typedef long long int ll;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    ll n;
    cin>>n;
    ll matrix[n+1][n+1];
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=n;j++)
        {
            matrix[i][j]=0;
        }
        matrix[i][i]=1;
    }
    vpll edges;
    ll pointer1=n;
    ll pointer2=1;
    if(n%2==1)
    {
        pointer1--;
    }
    while(pointer1>pointer2)
    {
        matrix[pointer2][pointer1]=1;
        matrix[pointer1][pointer2]=1;
        pointer2++;
        pointer1--;
    }
    for(ll i=1;i<n;i++)
    {
        for(ll j=1;j<=n;j++)
        {
            matrix[i][j]=1-matrix[i][j];
        }
    }
    for(ll i=1;i<=n;i++)
    {
        for(ll j=i+1;j<=n;j++)
        {
            if(matrix[i][j])
            {
                edges.push_back(make_pair(i,j));
            }
        }
    }
    ll size=edges.size();
    cout<<size<<endl;
    for(ll i=0;i<size;i++)
    {
        cout<<edges[i].first<<" "<<edges[i].second<<endl;
    }
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cassert>
#include <functional>
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; }

const long long INF = 1LL << 60;

int n;
long long h[100010];

long long dp[100010];


int main(){

	cin >> n;

	int ans = 0;

	if(n > 99999){
		n = 99999;
	}
	if(n > 9999){
		ans += n - 9999;
		n = 9999;
	}
	if(n > 999){
		n = 999;
	}
	if(n > 99){
		ans += n - 99;
		n = 99;
	}
	if(n > 9){
		n = 9;
	}
	if(n > 0){
		ans += n;
		n = 0;
	}

	cout << ans << endl;

	return 0;
}

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

using namespace std;


void solve() {
    int n; cin >> n;
    vector<pair<int, int>> a(n);
    int R = 2e9, L = 0, D = 0;
    for (int i = 0; i < n; i++) {
        int l,r;
        cin >> l >> r;
        r++;
        R = min(R, r);
        L = max(L, l);
        D = max(D, r - l);
        a[i] = {l, r};
    }
    int res = D + max(0, R - L);
    for (auto& p: a) {
        p.first = max(0, R - p.first);
        p.second = max(0, p.second - L);
    }
    sort(a.begin(), a.end(), [&](auto& u, auto& v){
            return u.first < v.first || (u.first == v.first && u.second > v.second);
            });
    int mi = a[0].second;
    for (int i = 1; i < n; i++) {
        res = max(res, mi + a[i].first);
        mi = min(mi, a[i].second);
    }
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define MAIN 200010
using namespace std;
int main()
{
    int n,a[110];
    while(cin>>n)
    {
        int maxx=0,posm=0;
        for(int i=1; i<=n; i++)
        {
            cin>>a[i];
            if(i==1) maxx=abs(a[i]),posm=i;
            else if(abs(a[i])>maxx) maxx=abs(a[i]),posm=i;
        }
        cout<<n*2-2<<endl;
        for(int i=1; i<=n; i++)
            if(i!=posm)
                cout<<posm<<" "<<i<<endl;
        if(a[posm]>=0)
        {
            for(int i=1; i<n; i++)
                cout<<i<<" "<<i+1<<endl;
        }
        else for(int i=n; i>1; i--)
            cout<<i<<" "<<i-1<<endl;
    }
    return 0;
}


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

using namespace std;
constexpr int INF = 1000000000;
constexpr int AREA_MAX = 1000010;

char flatGrid[AREA_MAX];
set<int> byRow[AREA_MAX], byCol[AREA_MAX];

int main() {
	int h, w, k; scanf("%d %d %d", &h, &w, &k);
	int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
	--x1, --y1, --x2, --y2;
	for (int i = 0; i < h; ++i) {
		scanf("%s", flatGrid + i * w);	
	}
	auto getCell = [&h, &w] (int i, int j) {
		return flatGrid[i * w + j];
	};
	auto deleteCell = [] (int i, int j) {
		byRow[i].erase(j);
		byCol[j].erase(i);
	};
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			byRow[i].insert(j);
			byCol[j].insert(i);
		}
	}
	vector<vector<int>> dist(h, vector<int>(w, -1));
	queue<pair<int, int>> q;
	q.emplace(x1, y1);
	dist[x1][y1] = 0;
	deleteCell(x1, y1);
	while (!q.empty()) {
		int cx, cy; tie(cx, cy) = q.front(); q.pop();
//		printf("visit %d %d %d\n", cx, cy, dist[cx][cy]);
		int nx = cx, ny = cy;
		auto updateCell = [&cx, &cy, &q, &deleteCell, &dist] (int i, int j) {
//			printf("updating %d %d from %d %d\n", i, j, cx, cy);
			deleteCell(i, j);
			dist[i][j] = dist[cx][cy] + 1;
			q.emplace(i, j);
		};
		while (true) { // moving cy forward
			auto ncell = byRow[nx].upper_bound(ny);
			if (ncell == byRow[nx].end() || *ncell - cy > k || getCell(nx, *ncell) == '@') break;
			ny = *ncell;
			updateCell(nx, ny);
		}
		nx = cx, ny = cy;
		while (true) { // move cx forward
			auto ncell = byCol[ny].upper_bound(nx);
			if (ncell == byCol[ny].end() || *ncell - cx > k || getCell(*ncell, ny) == '@') break;
			nx = *ncell;
			updateCell(nx, ny);
		}
		nx = cx, ny = cy;
		while (true) { // move cy backward
			auto ncell = byRow[nx].lower_bound(ny);
			if (ncell == byRow[nx].begin()) break;
			auto nbcell = prev(ncell, 1);
			if (cy - *nbcell > k || getCell(nx, *nbcell) == '@') break;
			ny = *nbcell;
			updateCell(nx, ny);
		}
		nx = cx, ny = cy;
		while (true) { // move cx backward
			auto ncell = byCol[ny].lower_bound(nx);
			if (ncell == byCol[ny].begin()) break;
			auto nbcell = prev(ncell, 1);
			if (cx - *nbcell > k || getCell(*nbcell, ny) == '@') break;
			nx = *nbcell;
			updateCell(nx, ny);
		}
	}
	printf("%d\n", dist[x2][y2]);
	return 0;
}


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

int calTime(int h1, int m1, int h2, int m2, int k) {
    int awake_t;
    if ((h2-h1) >= 0) {
        awake_t = (h2-h1)*60 + (m2-m1);
    }
    return awake_t-k;
}

int main() {
    int h1,m1,h2,m2,k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int ans = calTime(h1, m1, h2, m2, k);
    cout << ans;
    return 0;
}

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


using namespace std;
int main(){
int a,b,c;

scanf("%d",&a);
scanf("%d",&b);scanf("%d",&c);


int s1=b-a;
int s2=c-b;

if(s1==s2){

    printf("YES");
}


else{

     printf("NO\n");



}




}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<sstream>
#include<string>
using namespace std;
#define rep(i,ii,n) for(int i=ii;i<n;i++)
#define inf INT_MAX
#define mod (1000000007LL)
#define ll long long 
#define ull unsigned long long 
#define all v.begin(),v.end()
#define vi vector<int>




int main(){ 
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int a,b,c,d;
    cin>>a>>b>>c>>d;

    while(a>0 && c>0){
        c-=b;
        if(a>0 && c>0)
            a-=d;

    }
    if(a<=0 && c>0)cout<<"No";
    else cout<<"Yes";
    

 return 0;   
}//main


Measured memory_bytes: 3612
// Problem : D-query
// Contest : SPOJ - Classical
// URL : https://www.spoj.com/problems/DQUERY/
// Memory Limit : 1536 MB
// Time Limit : 1500 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
#define pii pair<int,int>
#define vi vector<int>
#define vp vector<pair<int,int>>
#define f first
#define se second
#define all(v) (v).begin(),(v).end()
//#define for(i,st,en,1) for(int i=st;i<en;i++)
//#define for(i,st,en,-1) for(int i=st;i>=en;i--)
using namespace std;
void update(vi &bit,int x,int v){
	for(;x<=bit.size();x+=x&-x)
	bit[x]+=v;
}
int query(vi &bit,int x){
	int c=0;
	for(;x>0;x-=x&-x)
	c+=bit[x];
	return c;
}
vi loc(1000001,-1);
void solve()
{
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,q;scanf("%d%d",&n,&q);
vi v(n);
for(int i=0;i<n;i++)
scanf("%d",&v[i]);
//vi loc(30001,-1);
vi bit(n+1);
vector<pair<pii,int>> v2(q);
for(int i=0;i<q;i++){
	int l,r;
 scanf("%d%d",&l,&r);
	v2[i].f={l,r};
 v2[i].se=i;
}
sort(all(v2),[](pair<pii,int> p1,pair<pii,int> p2){return p1.f.se<p2.f.se;});
int r=0;
vi ans(q);
for(int i=0;i<n;i++){
	//cerr<<i<<"\n";
	if(loc[v[i]]!=-1)
	update(bit,loc[v[i]],-1);
	update(bit,i+1,1);
	loc[v[i]]=i+1;
	int xt=query(bit,i+1);
	while(r<q and v2[r].f.se==i+1)
	{
		ans[v2[r].se]=xt-query(bit,v2[r].f.f-1);
		r++;
	}
}
for(int i=0;i<q;i++)
printf("%d\n",ans[i]);
}

int32_t main(){
//ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
}


Measured memory_bytes: 19368
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
using namespace std;
int a;
string s; 
int ans,maxn=0;
int main()
{
	cin>>a>>s;
	for(int i=0; i<a; i++)
	{
		if(s[i]=='I')
			ans++;
		else 
			ans--;
		if(ans>maxn)
			maxn=ans;
	}
	cout<<maxn<<endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <string>
#include <iostream>
#include <complex>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <stack>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <random>
#include <set>
#include <vector>
#include <unordered_map>
#include <bitset>
#include <unordered_set>
#include <array>
#include <forward_list>
//#include <chrono>
#include <iomanip>
#include <utility>
#include <assert.h>

#pragma GCC optimize("Ofast")
#pragma target("sse", "sse1")

#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

mt19937 gen(34);

string s;

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	//	freopen("memory.in", "r", stdin);
	//	freopen("memory.out", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> s;
	int ans = 0;
	for (int i = 0; i < s.length(); i++)
		ans += (s[i] != s[s.length() - 1 - i]);
	cout << ans / 2;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF 1e18
#define INF 1e9
using namespace std;

#define fs first
#define sc second

using P = pair<ll,ll>;
using PQ = priority_queue<P,vector<P>,greater<P>>;

signed main(){
    ll n,m;
    cin >> n >> m;

    vector<ll> G[n];
    vector<ll> dest(n);
    fill(dest.begin(),dest.end(),LINF);

    ll a,b;
    rep(i,0,m){
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    ll cnt = 0;
    queue<ll> q;
    q.push(0);
    while(!q.empty()){
        ll v = q.front();
        q.pop();

        rep(i,0,G[v].size()){
            if(dest[G[v][i]] == LINF){
                dest[G[v][i]] = v+1;
                q.push(G[v][i]);
                cnt++;
            }
        }
        
    }

    if(cnt != n) cout << "No" << endl;
    else{
        cout << "Yes" << endl;
        rep(i,1,n){
            cout << dest[i] << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 12952
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define PRINT(x) cout<<(x)<<endl
#define INF 1000000000000 // 10^12
#define MOD 1000000007 // 10^9+7
#define PB push_back
#define MP make_pair

const int MAX_NUM = 3000000;

vector<ll> mf(MAX_NUM, -1);
ll modfac(ll n, ll mod) {
    if (mf[n] != -1) return mf[n];
    if (n == 0) return mf[0] = 1;
    return mf[n] = n * modfac(n-1, mod) % mod;
}

ll modinv(ll a, ll mod) {
    ll b = mod, u = 1, v = 0;
    while(b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}

vector<ll> mif(MAX_NUM, -1);
ll modinvfac(ll n, ll mod) {
    if (mif[n] != -1) return mif[n];
    if (n == 0) return mif[0] = 1;
    return mif[n] = modinv(n, mod) * modinvfac(n-1, mod) % mod;
}

ll modcomb(ll n, ll k, ll mod) {
    return modfac(n, mod) * modinvfac(k, mod) % mod * modinvfac(n-k, mod) % mod; 
}

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

int main() {
    ll K;
    string S;
    cin >> K >> S;
    ll N = S.size();
    ll ans = 0;
    for (ll l = 0; l <= K; l++) {
        ans = (ans + modcomb(N+K-l-1, N-1, MOD) * modpow(25, K-l, MOD) % MOD * modpow(26, l, MOD)) % MOD;
    }
    PRINT(ans);
}

Measured memory_bytes: 113676
n = int(input())
action = []
for i in range(n):
    action.append(list(map(int, input().split())))
DP = [[0, 0, 0] for i in range(n + 1)]

for i in range(1, n + 1):
    for j in range(3):
        for k in range(3):
            if j != k:
                DP[i][k] = max(DP[i][k], DP[i - 1][j] + action[i - 1][k])

print(max(DP[-1]))

Measured memory_bytes: 47324
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    c=list(input())
    w=[0]*(N+1)
    r=[0]*(N+1)
    
    for i in range(N):
        if c[i]=="W":
            w[i+1]+=1
        else:
            r[i]+=1
            
    for i in range(N):
        w[i+1]+=w[i]
        
    for i in range(N,0,-1):
        r[i-1]+=r[i]
        
    ans=N
    for i in range(N+1):
        temp=max(w[i],r[i])
        ans=min(ans,temp)
        
    print(ans)

        
            

    

main()


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

bool check(string s) {
  if (s.size()%2 != 0) return false;
  else {
    if (s.substr(s.size()/2) == s.substr(0,s.size()/2)) {
      return true;
    }
    else return false;
  }
}

int main() {
  string s;
  cin >> s;
  int ans = 1;
  int l = s.size();
  s = s.erase(s.size() - 1);
  while (! check(s)) {
    s = s.erase(s.size()-1);
    ans++;
  }
    
  cout << l-ans << endl;  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define rep(i, n) for(ll i=0; i<(ll)(n); i++)
#define repd(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=b-1; (ll)(a)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
string YES[2] = {"NO", "YES"};
string yes[2] = {"No", "Yes"};

int main(){
    ll n, x, m; cin >> n >> x >> m;
    ll a = x, res=0;
    set<ll> st;
    vector<ll> key;
    map<ll, ll> mp;
    while(st.find(a)==st.end() && key.size()<n){
        st.insert(a);
        mp[a] = key.size();
        key.push_back(a);   res += a;
        a = (a*a)%m;    
    }
    //cout << res << endl;
    //rep(i, key.size()) cout << key[i] << ' ';
    if(0<a && n!=key.size()){
        vector<ll> v;
        ll loop=0;
        FOR(i, mp[a], key.size()){
            v.push_back(key[i]);    loop += key[i];
        }
        
        res += (n-key.size())/v.size()*loop;
        ll left = (n-key.size())%v.size();
        rep(i, left) res += v[i];
    }
    cout << res << endl;
}


Measured memory_bytes: 9796
N = int(input())
A = []
xy = []
for _ in range(N):
    a = int(input())
    A.append(a)
    tmp = []
    for _ in range(a):
        tmp.append(tuple(map(int, input().split())))
    xy.append(tmp)
ans = 0
for i in range(2**N)[::-1]:
    is_honest = [0] * N
    for idx, c in enumerate(bin(i)[2:][::-1]):
        if c == "1":
            is_honest[idx] = 1

    flag = True
    for i in range(N):
        a = A[i]
        for j in range(a):
            x, y = xy[i][j][0], xy[i][j][1]
            if is_honest[i]:
                if is_honest[x-1] != y:
                    flag = False
                    break
        if not flag:
            break
    if flag:
        ans = max(ans, sum(is_honest))
print(ans)

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

int comp(int *self, int *other){
    return *other - *self;
}

int main(){
    int i;
    int val[10];
    
    for(i = 0; i < 10; ++i){
        scanf("%d", &val[i]);
    }
    
    qsort(val, 10, sizeof(int), (int(*)(const void*, const void*))comp);
    
    for(i = 0; i < 3; ++i){
        printf("%d\n", val[i]);
    }
    
    return 0;
}


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


void solve() {
    long long x, y;
    cin >> x >> y;
    long long ans = 0;
    long long t = 1;
    while (x * t <= y) {
        t <<= 1;
        ans++;
    }
    cout << ans;
}


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


Measured memory_bytes: 3620
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 * @author sutoh
 *
 */
public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);
		int a,b,c;


		a=sc.nextInt();
		b=sc.nextInt();
		c=sc.nextInt();

		List<Integer> list=new ArrayList<Integer>();

		list.add(a);
		list.add(b);
		list.add(c);

		Collections.sort(list);

		System.out.println(list.get(0)+list.get(1));


	}

}


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

#define MOD 1000000007

typedef long long lli;

lli d[301][301][301];
int n, m;

lli f(int scc1, int vis, int k) {
	if (k == m) return scc1 == n && vis == n;
	if (d[scc1][vis][k] >= 0) return d[scc1][vis][k];
	lli res = (n - vis)*f(scc1, vis + 1, k + 1) % MOD;
	res += (vis - scc1)*f(scc1, vis, k + 1) % MOD; res %= MOD;
	res += scc1*f(vis, vis, k + 1) % MOD; res %= MOD;
	return d[scc1][vis][k] = res;
}

int main() {
	scanf("%d %d", &n, &m);
	memset(d, -1, sizeof(d));
	printf("%lld\n", f(1, 1, 0));
	return 0;
}

Measured memory_bytes: 213248
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.
// insert #if<tab> by my emacs. #if DEBUG == 1 ... #end

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

ll Q, H, S, D;
ll N;

int main () {
  cin >> Q >> H >> S >> D;
  cin >> N;
  N *= 4;
  ll one = Q;
  ll two = min(H, one * 2);
  ll four = min(S, two * 2);
  ll eight = min(D, four * 2);
  ll ans = 0;
  ans += N/8 * eight;
  N %= 8;
  ans += N/4 * four;
  N %= 4;
  ans += N/2 * two;
  N %= 2;
  ans += N * one;
  cout << ans << endl;
}


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

using namespace std;

int h, w, n;

bool Check(vector<string> field)
{
    bool change = true;

    while (true) {
        change = false;

        for (int j = 0; j < w; ++j) {
            int idx = h - 1;

            while (idx >= 0) {
                if (field[idx][j] == '.') {
                    int nxt = idx - 1;
                    while (nxt >= 0) {
                        if (field[nxt][j] != '.')
                            break;
                        else
                            --nxt;
                    }
                    if (nxt < 0)
                        break;
                    swap(field[idx][j], field[nxt][j]);
                    --idx;
                }
                else
                    --idx;
            }
        }

        vector<string> tmp = field;
        for (int i = h - 1; i >= 0; --i) {
            for (int j = 0; j < w; ++j) {
                if (field[i][j] == '.')
                    continue;

                // right
                int len = 1;
                while (len + j < w) {
                    if (field[i][j] != field[i][len + j])
                        break;
                    ++len;
                }
                if (n <= len) {
                    for (int t = 0; t < len; ++t)
                        tmp[i][t + j] = '.';
                    change = true;
                }

                // down
                len = 1;
                while (i - len >= 0) {
                    if (field[i][j] != field[i - len][j])
                        break;
                    ++len;
                }
                if (n <= len) {
                    for (int t = 0; t < len; ++t)
                        tmp[i - t][j] = '.';
                    change = true;
                }
            }
        }

        field = tmp;
        if (!change)
            break;
    }

    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            if (field[i][j] != '.')
                return false;
    return true;
}

bool Solve(vector<string> &field)
{
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w - 1; ++j) {
            if (field[i][j] == field[i][j + 1])
                continue;
            swap(field[i][j], field[i][j + 1]);
            if (Check(field))
                return true;
            swap(field[i][j], field[i][j + 1]);
        }

    return false;
}

int main()
{
    cin >> h >> w >> n;

    vector<string> field(h);
    for (int i = 0; i < h; ++i)
        cin >> field[i];

    if (Solve(field))
        cout << "YES\n";
    else
        cout << "NO\n";

    return 0;
}

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

#define watch(x) cerr << (#x) << ": " << (x) << endl
#define int long long



int32_t main() {

    char b; cin >> b;
    if(b == 'A') cout << 'T';
    else if(b == 'T') cout << 'A';
    else if(b == 'G') cout << 'C';
    else cout << 'G';

    cout << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) int(a.size())
const int N=4e6+10;

int gi() {
	int x=0,o=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') o=-1,ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*o;
}

int n,m,k,s[N],t[N],tt,pos;
list<int> q[N];

struct dat {
	int op,t;
	int gettim() {
		if(op<=2) return t;
		return q[t].front()+pos;
	}
	//op:操作id
	//若op=1,2 t表示操作时间
	//else t表示对应维护操作的deque id
};

void read(int *a,int n) {
	static char s[N];
	scanf("%s",s);
	for(int i=0;i<n;i++) a[n-i-1]=s[i]-'0';
}

void print(int *a) {
	int p=N-1;
	while(!a[p]) --p;
	for(int i=p;~i;i--) putchar(a[i]+'0');
	cout<<'\n';
}

void print(vector<dat> eve) {
	for(auto x:eve) {
		if(x.op<=2) cerr<<(x.op&1)<<' '<<(x.op>>1)<<' '<<x.t<<'\n';
		else {
			for(auto v:q[x.t]) cerr<<1<<' '<<1<<' '<<v+pos<<'\n';
		}
	}
}

void add(vector<dat> &eve,int x,int y,int tim) {
	if(!x&&!y) return;
	if(!x||!y) eve.pb((dat){x|(y<<1),tim});
	else if(!eve.empty()&&eve.back().op==3) q[eve.back().t].pb(tim-1-pos);
	else ++tt,q[tt].pb(tim-1-pos),eve.pb((dat){3,tt});
}

void add_list(vector<dat> &eve,int id) {
	if(!eve.empty()&&eve.back().op==3) q[eve.back().t].splice(q[eve.back().t].end(),q[id]);
	else eve.pb((dat){3,id});
}

int main() {
	cin>>n>>m>>k;
	read(s,n);read(t,m);
	vector<dat> eve;
	for(int i=0;i<n||i<m||!eve.empty();i++) {
		pos=i;
		int cur_t=1;
		vector<dat> new_eve;
		eve.pb((dat){0,k+1});
		for(auto x:eve) {
			if(cur_t<x.gettim()&&s[i]&&t[i]) {
				//cerr<<i<<'\n';
				s[i]=t[i]=0;
				add(new_eve,1,1,cur_t);
			}
			cur_t=x.gettim();
			if(cur_t==k+1) break;
			if(x.op<=2) {
				int v=s[i]&t[i];
				int new_s=s[i]+v+(x.op&1),new_t=t[i]+v+(x.op>>1);
				s[i]=new_s&1;t[i]=new_t&1;
				add(new_eve,new_s>>1,new_t>>1,cur_t);
				++cur_t;
			}
			else {
				//cerr<<i<<' '<<cur_t<<'\n';
				if(s[i]+t[i]==1) {
					for(auto tmp:q[x.t]) {
						cur_t=tmp+pos;
						int v=s[i]&t[i];
						int new_s=s[i]+v+(x.op&1),new_t=t[i]+v+(x.op>>1);
						s[i]=new_s&1;t[i]=new_t&1;
						add(new_eve,new_s>>1,new_t>>1,cur_t);
						++cur_t;
					}
				}
				else {
					int tmp=0;
					if(s[i]&&t[i]) tmp=q[x.t].front()+pos;
					cur_t=q[x.t].back()+pos+1;
					q[x.t].pop_back();
					if(s[i]&&t[i]) q[x.t].push_front(tmp-pos-1);
					if(!q[x.t].empty()) add_list(new_eve,x.t);
					s[i]=t[i]=1;
				}
			}
		}
		swap(eve,new_eve);
	}
	print(s);print(t);
	return 0;
}


Measured memory_bytes: 136320
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

int main() {
    int n, ans;
    int a[105];

    scanf("%d", &n);

    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans, abs(a[i] - a[j]));
        }
    }

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

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define RI register int
typedef long long LL;

#define FILEIO(name) freopen(name".in", "r", stdin), freopen(name".out", "w", stdout);

using namespace std;

char buf[1000000], *p1 = buf, *p2 = buf;
inline char gc() {
  if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
  return p1 == p2 ? EOF : *(p1++);
}
template <class T> inline void read(T &n) {
  n = 0; RI ch = gc(), f;
  while ((ch < '0' || ch > '9') && ch != '-') ch = gc();
  f = (ch == '-' ? ch = gc(), -1 : 1);
  while (ch >= '0' && ch <= '9') n = n * 10 + (ch ^ 48), ch = gc();
  n *= f;
}

int const MAXN = 2e5 + 5, BI = 2001, mod = 1e9 + 7;
int x[MAXN], y[MAXN];
int f[4005][4005];
LL frac[MAXN], invfrac[MAXN];

inline LL qpow(LL a, LL k) {
  LL re = 1;
  for (; k; k >>= 1, a = a * a % mod)
    if (k & 1) re = re * a % mod;
  return re;
}
inline LL C(int n, int m) { return frac[n] * invfrac[m] % mod * invfrac[n - m] % mod; }

int main() {
  
#ifdef LOCAL
  FILEIO("a");
#endif

  int n; read(n);
  for (RI i = 1; i <= n; ++i)
    read(x[i]), read(y[i]), f[BI - x[i]][BI - y[i]] += 1;
  frac[0] = 1;
  for (RI i = 1; i <= BI * 4; ++i) frac[i] = frac[i - 1] * i % mod;
  invfrac[BI * 4] = qpow(frac[BI * 4], mod - 2);
  for (RI i = BI * 4; i; --i) invfrac[i - 1] = invfrac[i] * i % mod;
  for (RI i = 1; i <= BI + BI; ++i)
    for (RI j = 1; j <= BI + BI; ++j)
      f[i][j] = ((f[i][j] + f[i - 1][j]) % mod + f[i][j - 1]) % mod;
  LL ans = 0;
  for (RI i = 1; i <= n; ++i)
    ans = (ans + f[x[i] + BI][y[i] + BI] - C(x[i] * 2 + y[i] * 2, x[i] * 2)) % mod;
  cout << (ans + mod) % mod * 500000004 % mod<< endl;

  return 0;
}

// created by Daniel yuan


Measured memory_bytes: 66816
def gcd(a,b):
	while a>0 and b>0:
		if a<b:
			b -= a
		elif a>b:
			a -= b
		else:
			return a
	raise

def lcm(a,b):
	return a*b/gcd(a,b)


while True:
	try:
		inp = raw_input()
	except EOFError:
		break
	a, b = map((lambda x: int(x) ), inp.split())

	print gcd(a,b),lcm(a,b)

Measured memory_bytes: 4220
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long int ll;
static const int MAX_N = 100;
static const int MAX_K = 100000;
static const ll MOD = 1000000007;

int N, K;
int a[MAX_N + 1];
ll memo[MAX_N + 1][MAX_K + 1], memo2[MAX_N + 1][MAX_K + 2];

int main(){
	scanf("%d %d", &N, &K);
	for(int i = 1; i < N + 1; i++) scanf("%d", &a[i]);

	memo[0][0] = 1LL;
	int sum = 0;
	for(int j = 1; j <= K + 1; j++) memo2[0][j] = memo2[0][j - 1] + memo[0][j - 1];
	for(int i = 1; i < N + 1; i++){
		sum += a[i];
		for(int j = 0; j <= min(sum, K); j++){
			memo[i][j] = memo2[i - 1][j + 1] - memo2[i - 1][max(0, j - a[i])];
			while(memo[i][j] < 0) memo[i][j] += MOD;
			memo[i][j] %= MOD;
		}
		for(int j = 1; j <= K + 1; j++){
			memo2[i][j] = memo2[i][j - 1] + memo[i][j - 1];
			memo2[i][j] %= MOD;
		}
	}
	printf("%lld\n", memo[N][K]);
	return 0;
}


Measured memory_bytes: 157952
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

const int MX = 200010;
int cnt[MX], cov[MX], kind;
void add(int x){
	int pos = x - cnt[x]++;
	if(pos < 0) return;
	if(cov[pos]++ == 0) kind++;
}
void del(int x){
	int pos = x - --cnt[x];
	if(pos < 0) return;
	if(--cov[pos] == 0) kind--;
}

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	
	int n, m; cin >> n >> m;
	vi a(n);
	rep(i, n){
		cin >> a[i]; add(--a[i]);
	}
	rep(i, m){
		int x, y; cin >> x >> y; x--; y--;
		del(a[x]);
		add(a[x] = y);
		cout << n - kind << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3840
#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() {
    vector<double> a(3);
    rep(i,3) cin >> a.at(i);
    sort(a.begin(),a.end());
    cout << a.at(0)*a.at(1)/2 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
// make pair, tuple
// __gcd(int, int);
// bool isPrime(int n){
//       if(n <= 1)return false;
//       if(n <= 3)return true;
//       if(n % 2 == 0 || n % 3 == 0)return false;
//       for(int i = 5;i * i <= n;i += 6){
//             if(n % i == 0 || n % (i + 2) == 0)return false;
//       }
//       return true;
// }
// int countSubString(string s, string temp){
//       int ans = 0;
//       size_t f = s.find(temp);
//       while(f != string::npos){
//             ans++;
//             f = s.find(temp, f + 1);
//       }
//       return ans;
// }
// 
// #Count leading & trailing zero of an integer bits
// __builtin_clz(n);
// __builtin_clzll(n);
//
// #Count 1s bits of an integer
// __builtin_popcount(n);
// __builtin_popcountll(n);
//
// #Error checking
// assert(n == 3);
// 
// #Error Printing
// cerr << "Some thing";

int main(){
    long long int l,r;cin >> l >> r;
    r = min(r, l + 2020);
    long long int ans = 2018;
    for(long long int i = l;i < r;i++){
        for(long long int j = i + 1;j <= r;j++){
            ans = min(ans, (i * j) % 2019);
        }
    }
    cout << ans;
}

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

int N, M, d[101][101];

int bino(int n, int r) {
    if (n == 1) return 1;
    if (r == 0 || r == n) return 1;
    if (d[n][r]) return d[n][r];
    return bino(n-1,r-1) + bino(n-1,r);
}

int main() {
    scanf("%d%d", &N, &M);
    int ans = 0;
    if (N > 1) ans += bino(N,2);
    if (M > 1) ans += bino(M,2);
    printf("%d", ans);
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

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

    static class C {
        public void solve(int testNumber, MyScanner in, PrintWriter out) {
            int K = in.nextInt();
            int N = in.nextInt();
            int[] A = in.nextIntArray(N);
            int ans = K + A[0] - A[N - 1];
            for (int i = 0; i < N - 1; i++) {
                ans = Math.max(ans, A[i + 1] - A[i]);
            }
            out.println(K - ans);
        }

    }

    static class MyScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public MyScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

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

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

        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

    }
}



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

int main() {
	int m, n;
	cin >> m >> n;
	int a[20] = {};
	for (int i = 0;i < m;i++) {
		for (int j = 0;j < n;j++) {
			int b;
			cin >> b;
			a[i] += b;
		}

	}
	sort(a, a + 20);
	cout << a[19] << endl;
}


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


using namespace std;

typedef pair<int, int> P;

long long x, ans;

int main() {
    cin >> x;
    long long n = 100;
    for (int i = 1; i < 10000; i++) {
        n += n / 100;
        if (n >= x) {
            cout << i << endl;
            return 0;
        }
    }
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpl;
typedef vector<vll> vvll;

#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define no cout<<"No"<<endl
#define NO cout<<"NO"<<endl
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

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

  ll n;
  cin>>n;
  vll a(n);
  REP(i,n)cin>>a[i];

  ll last=a[0];
  ll ans=0;
  REP(i,n){
    if(i==0)
      continue;

    ans+=max(last-a[i],0LL);
    last=max(last,a[i]);
  }

  cout<<ans<<endl;

}



Measured memory_bytes: 4760
import sys
#from me.io import dup_file_stdin

#@dup_file_stdin
def solve():
    for line in sys.stdin:
        a,b,c,d,e,f=map(float,line.split(' '))
        print("{:.3f} {:.3f}".format((c*e-b*f)/(a*e-b*d)+0,(c*d-a*f)/(b*d-a*e)+0))
solve()

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

#define INF_LL 1e18
#define INF 1e9

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

#define fst first
#define snd second

using namespace std;

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

vector<int> g[5005];
vector<int> G[5005];
int C[5005], R[5005];
bool flag[5005];

void dfs(int base, int now, int dis, int before){
	if(dis >= R[base]) return;
	//if(flag[now]) return;
	flag[now] = true;
	REP(i, g[now].size()){
		if(g[now][i] == before) continue;
		G[base].push_back(g[now][i]);
		dfs(base, g[now][i], dis+1, now);
	}
}

struct state{int now, dis, before;};

int main(void){
	int N, K;
	cin >> N >> K;
	REP(i, N){
		cin >> C[i] >> R[i];
	}
	REP(i, K){
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	REP(i, N){
		memset(flag, 0, sizeof flag);
		queue<state> q;
		q.push({i, 0, i});
		while(q.size()){
			state s = q.front(); q.pop();
			if(s.dis >= R[i]) continue;
			if(flag[s.now]) continue;
			flag[s.now] = true;
			REP(j, g[s.now].size()){
				if(g[s.now][j] == s.before) continue;
				G[i].push_back(g[s.now][j]);
				q.push({g[s.now][j], s.dis+1, s.now});
			}
		}
	}
	priority_queue<PII, vector<PII>, greater<PII> > pq;
	ll d[5005];
	fill(d, d+5005, INF_LL);
	d[0] = 0;
	pq.push({0, 0});
	while(pq.size()){
		PII p = pq.top(); pq.pop();
		int v = p.second;
		if(d[v] < p.first) continue;
		REP(i, G[v].size()){
			if(d[G[v][i]] > d[v] + C[v]){
				d[G[v][i]] = d[v] + C[v];
				pq.push({d[G[v][i]], G[v][i]});
			}
		}
	}
	cout << d[N-1] << endl;
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  int x;
  for(int i = 0; i<N; i++){
  int a, b;
  cin>>a>>b;
  x=x+(b-a)+1;
  }
  
  cout<<x<<endl;
}


Measured memory_bytes: 256
def count(s1,s2):
	cnt = 0
	for i in range(len(s2)):
		if s1[i] != s2[i]:
			cnt += 1
	return cnt 


S1 = input()
S2 = input()

mmin = len(S2)
for i in range(len(S1)-len(S2)+1):
	k = count(S1[i:len(S2)+i],S2)
	if k < mmin:
		mmin = k

print(mmin)



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

#define reps(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   reps(i,0,n)
#define all(x) (x).begin(),(x).end()
#define INF (2000000000)
#define MOD (1000000007)
#define PI (acos(-1))

int main(){
  int n;
  cin >> n;
  int h[200000];
  int maxi=0;
  rep(i,n){
    cin >> h[i];
    maxi = max(h[i],maxi);
    if(maxi-h[i] >= 2){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define MM = 1e9;
#define mod = MM + 7;
#define INF (ll)1e18
#define PI acos(-1.0)
#define NIL -1
#define rep(i, n) for(int i = 0; i < n; i++)
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int main(){
    int n,k; cin >> n >> k;
    int a[n];
    map<int,int> mp;
    int cnt = 0;
    int ans = 0;
    rep(i,n){
        cin >> a[i];
        if(mp[a[i]] == 0) cnt++;
        mp[a[i]]++;
    }
    if(cnt <= k){
        cout << 0 << endl;
        return 0;
    }
    vector<int> v(0);
    rep(i,n){
        if(mp[i] != 0) v.push_back(mp[i]);
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    for(int i = 0; i < k; i++){
        ans += v[i];
    }
    cout << n-ans << endl;
}

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

int main(){
  int N,M; cin>>N>>M;
  vector<vector<int>> G(N);
  vector<int> P(N,0);
  vector<int> path(N,0);
  int x,y;
  for(int i=0;i<M;i++){
    cin>>x>>y;
    x--; y--;
    P[y]++;
    G[x].push_back(y);
  }
  queue<int> q;
  for(int i=0;i<N;i++){
    if(!P[i])
      q.push(i);
  }
  while(!q.empty()){
    x=q.front(); q.pop();
    for(int j=0;j<G[x].size();j++){
      y=G[x][j];
      path[y]=max(path[y],path[x]+1);
      P[y]--;
      if(!P[y]){
        q.push(G[x][j]);
      }
    }
  }
  sort(path.begin(),path.end());
  cout<<path[N-1]<<endl;
}

Measured memory_bytes: 6528
n = int(input())
t = list(map(int,input().split()))
m = int(input())
px = [[int(i) for i in input().split()] for i in range(m)]
for i in range(m):
    ans = 0
    for j in range(n):
        if px[i][0] == j+1:
            ans += px[i][1]
        else:
            ans += t[j]
    print(ans)
    


Measured memory_bytes: 38896
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

inline int toInt(string s) {int v; istringstream sin(s);sin>>v; return v;}

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vector<int> > Mat;
typedef tuple<int, int, int, int> T;

const int MOD = (int)1e9+7;
const int INF = (int)1e9;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

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

    int x;
    cin >> x;
    cout << 24+(24-x) << endl;

    return 0;
}

Measured memory_bytes: 256
n=int(input())
data=[list(map(int,input().split())) for i in range(n)]
data.sort(key=lambda x:x[2],reverse=True)
def cal(y,x,datum,height):
  return max(height-(abs(y-datum[1])+abs(x-datum[0])),0)==datum[2]
for i in range(101):
  for j in range(101):
    height=abs(i-data[0][1])+abs(j-data[0][0])+data[0][2]
    flag=0
    for k in data[1:]:
      if not cal(i,j,k,height):
        flag=1
        break
    if flag:pass
    else:print(j,i,height);exit()


Measured memory_bytes: 3064
#include <iostream>

using namespace std;

int main(void) {
    int N, D, X;
    int a[100];
    int res;
    cin >> N >> D >> X;
    res = X;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        if (D % a[i] == 0) {
            res += D / a[i];
        } else {
            res += D / a[i] + 1;
        }
    }
    cout << res;
    return 0;
}

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

#define rep(i,n) for(int i = 0; i < (n); ++i)

signed main()
{
    int n,k; cin >> n >> k;
    string s; cin >> s;

    s[k-1] += 'a' - 'A';

    cout << s << endl;

    return 0;
}


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

using namespace std;

int main(void)
{
    string a, b, c;
    
    cin >> a >> b >> c;

    if(a[a.size()-1] == b[0] && b[b.size()-1] == c[0]){
        cout << "YES" << endl;
    }

    else{
        cout << "NO" << endl;
    }

    return 0;
}

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> vec(n);
    rep(i, n) cin >> vec[i];
    sort(all(vec));
    int sum = 0;
    rep(i, k) sum +=  vec[i];
    cout << sum << endl;
    return 0;
}

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

using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define int long long
const long long INF=1e18;
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long, long > > vpll;
typedef vector<pair<int, int > > vpii;


int32_t main() {
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    
    
    ini(n);
    ini(n1);
    int tmpll = -1,tmprr = n+1;
    FOR(i,0,n1){
        ini(x);
        ini(x1);
        tmpll = max(tmpll,x);
        tmprr = min(tmprr,x1);
    }
    if(tmpll>tmprr){out(0);}
    else
    out(tmprr-tmpll+1);
  
    
    
    
    
    
    
    
    return 0;
}


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

int main(){
    int x1,y1,x2,y2,x3,y3,x4,y4;
    cin >> x1 >> y1 >> x2 >> y2;
    int x = x2-x1,y = y2-y1;
    cout << x2-y << " " << y2+x << " " << x1-y << " " <<  y1+x << endl;
    return 0;
}

Measured memory_bytes: 256