akhauriyash/Code-Regression huggingface dataset:
// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std, core.bitop;
// dfmt on
void main()
{
    long H, W;
    scan(H, W);
    long CH, CW;
    scan(CH, CW);
    CH--, CW--;
    long DH, DW;
    scan(DH, DW);
    DH--, DW--;
    auto S = new string[](H);
    foreach (i; 0 .. H)
    {
        S[i] = sread();
    }
    alias T = Tuple!(long, long, long);
    PQueue!T Q;
    Q.insert(T(0, CH, CW));
    auto visited = new bool[][](H, W);
    long cnt;
    while (!Q.empty)
    {
        cnt++;
        auto t = Q.front;
        auto d = t[0];
        auto y = t[1];
        auto x = t[2];
        Q.removeFront();
        if (visited[y][x])
            continue;
        visited[y][x] = true;
        dprint(t);
        if (S[y][x] == '#')
            continue;
        if (y == DH && x == DW)
        {
            writeln(d);
            return;
        }
        foreach (a; -2 .. 2 + 1)
            foreach (b; -2 .. 2 + 1)
            {
                if (a == 0 && b == 0)
                    continue;
                if (y + a < 0 || H <= y + a)
                    continue;
                if (x + b < 0 || W <= x + b)
                    continue;
                if (visited[y + a][x + b])
                    continue;
                if (S[y + a][x + b] == '#')
                    continue;
                if (abs(a) <= 1 && b == 0)
                {
                    Q.insert(T(d, y + a, x + b));
                    continue;
                }
                if (a == 0 && abs(b) <= 1)
                {
                    Q.insert(T(d, y + a, x + b));
                    continue;
                }
                Q.insert(T(d + 1, y + a, x + b));
            }
    }
    writeln(-1);
    dprint(cnt);
}


Measured memory_bytes: 7240
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); cout << '\n';}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); cout << '\n';}
template <typename T>
void ce(const T n){cerr << n << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
constexpr ll INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr ll MOD = 1e9+7;
//constexpr ll MOD = 998244353;
constexpr ld PI = acos(-1);
constexpr ld EPS = 1e-11;

ll n;

void dfs(string s, ll pos, char max){
	if(pos == n){
		co(s);
		return;
	}

	char en = s.back();
	for(char c = 'a'; c <= max + 1; ++c){
		s.pb(c);
		char tmp = max;
		chmax(tmp, c);
		dfs(s, pos + 1, tmp);
		s.pop_back();
	}
}

int main(void){
	cin >> n;

	dfs("a", 1, 'a');

	return 0;
}


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

using namespace std;

int main(void){
    int N, D, X;
    cin >> N >> D >> X;
    int ans = X;
    for(int i=0;i<N;i++){
        int A;
        cin >> A;
        ans += (D-1)/A+1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <cassert>
#include <string>
#include <cmath>
#include <iomanip>

using namespace std;
using ll = long long;
using ld = long double;

#define st first
#define nd second

const int MAXN = 1e6 + 5, inf = 1e9;
const ll INF = 1e18;
const ld PI = 3.1415926535897932384626433832795;

int cnt[MAXN];
ll dp[MAXN], tab[MAXN], h[MAXN];
bool vis[MAXN], used[MAXN];

vector<int> G[MAXN];
vector<ll> V;
set<ll> S;
map<ll, int> M;
stack<ll> St;
queue<ll> Q;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout << setprecision(13) << fixed;

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

    int n, k;
    cin >>  n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    for (int i = 2; i <= n; i++) {
        dp[i] = INF;
        for (int j = i - 1; j > max(i - k - 1, 0); j--) {
            dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]));
        }
    }
    cout << dp[n] << "\n";
}


Measured memory_bytes: 29056
import java.util.Arrays;
import java.util.stream.IntStream;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        while(true){
            int n = sc.nextInt();
            int r = sc.nextInt();
            if(n == 0 || r == 0){
                break;
            }

            int x[] = new int[n];

            int i;
            for(i=0; i<n; i++){
                x[i] = n - i;
            }

            int j;
            for(j=0; j<r; j++){
                int p = sc.nextInt();
                int c = sc.nextInt();
                IntStream stream1 = Arrays.stream(Arrays.copyOfRange(x, p-1, p+c-1));
                IntStream stream2 = Arrays.stream(Arrays.copyOfRange(x, 0, p-1));
                IntStream stream3 = Arrays.stream(Arrays.copyOfRange(x, p+c-1, n));
                IntStream s = IntStream.concat(IntStream.concat(stream1, stream2),stream3);
                x = s.toArray();
            }

            System.out.println(x[0]);
        }

        sc.close();

    }
}


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

int main()
{
    int h,m,s,t;
    while (1)
    {
	cin >> h >> m >> s;
	if (h==-1)break;
	t = 120*60-(h*3600+m*60+s);
	printf("%02d:%02d:%02d\n",t/3600,(t/60)%60,t%60);
	t*=3;
	printf("%02d:%02d:%02d\n",t/3600,(t/60)%60,t%60);
    }
    return 0;
}

Measured memory_bytes: 0
n = int(input())
a = list(map(int, input().split()))
cmin = ((max(a) - min(a)) ** 2) * n
for x in range(min(a), max(a) + 1):
    c = 0
    for i in a:
        c += (i - x) ** 2
    cmin = min(c, cmin)
print(cmin)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (int i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,v) for (int i = 0; i < v.size(); i++)
#define RREPALL(i,v) for (int i = v.size()-1; i >= 0; i--)
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(v.begin(), v.end())
#define MIN_ELEMENT(v) min_element(v.begin(), v.end())
#define MAX_ELEMENT(v) max_element(v.begin(), v.end())
#define COUNT(v,n) count(v.begin(), v.end(), n)
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e7;
const ll MOD = 1e9 + 7;

int h, w;

int main()
{
    while (cin>>h>>w, h != 0) {
        REP(i,h) {
            REP(j,w) {
                cout<<((i + j) % 2 == 0 ? '#' : '.');
            }
            putchar('\n');
        }
        putchar('\n');

    }

    return 0;
}




Measured memory_bytes: 3076
import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException
    {
         
        int tmp;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        if(a > b) {
            tmp = a;
            a = b;
            b = tmp;
        }if(b > c) {
            tmp = b;
            b = c;
            c = tmp;
        }if(a > b){
            tmp = a;
            a = b;
            b = tmp;
        }
        System.out.println(a +" "+ b +" "+ c);
    }       
}

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

using ll = long long;

const int INF = 1001001001;
const ll INF_LL = 1001001001001001001LL;

int main(void){
  string a,b,c; cin >> a >> b >> c;
  bool ok = true;
  if(a[a.size()-1] != b[0]) ok = false;
  if(b[b.size()-1] != c[0]) ok = false;

  if(ok) cout << "YES" << endl;
  else cout << "NO" << endl;
  
  return 0;
}


Measured memory_bytes: 3648
def insertionSort(n,a):
    for i in range(1,n):
        x = a[i]
        j = i
        print(*a)
        while j>0 and x < a[j-1]:
            a[j] = a[j-1]
            j -= 1
            a[j] = x

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    insertionSort(n,a)
    print(*a)



Measured memory_bytes: 5980
#include <iostream>

using namespace std;

int main(void)
{
  int N, X;

  cin >> N;

  X = (int)((N + 1)/ 1.08);

  if ((int)(X * 1.08) == N) {
    cout << X;
  } else {
    cout << ":(";
  }

  return 0;
}


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

#define MOD 1000000007
LL powmod(LL a, LL n){
    if(n == 0) return 1;
    if(n % 2) return (a*powmod(a,n-1)) % MOD;
    LL c = powmod(a, n/2);
    return (c*c) % MOD;
}
LL inv(LL a){
    return powmod(a, MOD-2);
}
LL fact[1100000];
LL invfact[1100000];

LL ncr(LL n, LL r){
    if(r < 0 || n < 0) return 0;
    if(n < r) return 0;
    LL a = fact[n];
    a = (a * invfact[r]) % MOD;
    a = (a * invfact[n-r]) % MOD;
    return a;
}
void init(){
    fact[0] = 1;
    invfact[0] = 1;
    LL inv2 = inv(2);
    for(LL i = 1; i < 1100000; i++){
        fact[i] = (i*fact[i-1]) % MOD;
        invfact[i] = inv(fact[i]);
    }
}

int main(){
    init();
    LL A, B;
    cin >> A >> B;
    LL ans = 0;
    for(LL b = 1; b <= B; b++){
        // number of B's
        if(b == B){
            ans += (A+1);
            continue;
        }
        LL B2 = B - b;
        for(LL b2 = 1; b2 <= B2; b2++){
            LL num = ncr(B-1, b-1);
            num *= ncr(B2-1, b2-1);
            num %= MOD;

            LL B3 = B2 - b2;

            LL aleft = A+B - B - B2 - B3;
            if(aleft < 0) continue;
            num = num * ncr(aleft + 2, 2);
            num %= MOD;
            ans += num;
            ans %= MOD;
        }

    }
    cout << ans << endl;
}

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

int main() {
    int n;
    string s, t;
    cin >> n >> s >> t;
    rep(i, n) { cout << s[i] << t[i]; }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
//typedef pair<ll, ll> P;
//typedef pair<int, pair<int, int>> P;
//typedef pair<ll, pair<int, int>> P;
typedef pair<ll,pair<ll,ll>> T;
ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 2147483600;//10^9
int INFM =100000000;
ll MOD  = 1000000007;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
ll dp[100010][4];

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


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

int main(){
  int n,k,tmp;
  int s[100],b[100];
  bool f;

  while(1){
    cin >> n >> k;
    if(!n && !k)break;

    for(int i=0;i<k;i++){
      cin >> s[i];
      b[i] = 0;
    }

    for(int i=0;i<n;i++){
      for(int j=0;j<k;j++){
	cin >> tmp;
	b[j] +=tmp;
      }
    }

    f = true;
    for(int i=0;i<k;i++){
      if(b[i] > s[i]){
	f = false;
	break;
      }
    }
     
    if(f)cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}

Measured memory_bytes: 0
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String S = "";
		//HashSetで重複を許可しない空箱setを作成
		Set<String> set = new HashSet<String>();
		for(int i=0; i<N; i++) {
			S = sc.next();
		//setに重複を除いた景品名を入れる
			set.add(S);
		}
		//setに含まれる要素数を出力する
		System.out.println(set.size());
	}		
}

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

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



    for (int i = 1; i <= 1250; i++)
    {
        if( floor(i*0.08) == a and floor(i*0.1) == b)
        {
            cout << i << endl;
            return 0;
        }
    }

    cout << -1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <set>
#include <queue>
#include <stack>
#include <utility>
#include <stdio.h>
#include <unistd.h>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define drep(i, n) for(int i = n - 1; i >= 0; i--)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define PI 3.14159265359

const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const int mod = 1000000007;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

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

  ll ans = 0;
  int loop = pow(2, s.size() - 1);
  rep (i, loop) {
    ll now = s[0] - '0';
    for (int j = 1; j < s.size(); j++) {
      if (i & (1 << (j - 1))) {
        // P(now);
        ans += now;
        now = s[j] - '0';
      } else {
        now = now * 10 + (s[j] - '0');
      }
    }
    // P(now);
    ans += now;
  }
  P(ans);

  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repd(i,a,b) for (int i = (a); i < (b); i++)
#define INF LLONG_MAX
#define mod 1000000007
typedef long long ll;
int main(void)
{
	int N;
	cin >> N;
	ll C[N+1];
	rep(i, N+1) C[i] = 0;
	int A[N];
	rep(i, N)
	{
		cin >> A[i];
		C[A[i]]++;
	}

	ll ans = 0;
	repd(j, 1, N+1) if(C[j]>1) ans += C[j]*(C[j]-1)/2;
	rep(i, N)
	{
		if(C[A[i]]>1) cout << ans - (C[A[i]] - 1) << endl;
		else cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 4864
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<double> vd;
typedef pair<double,double> PD;
typedef pair<int,P> ed;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  string s;
  cin >> s;
  int len = sz(s);
  sort(rng(s));
  uni(s);
  if(len==sz(s)) {
    cout << "yes" << endl;
  } else {
    cout << "no" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
  int a,b;
  cin>>a>>b;
  
  if(a<b){
    for(int i=0;i<b;i++){
      cout<<a;
    }
  }else{
    for(int i=0;i<a;++i){
      cout<<b;
    }
  }
  cout<<endl;
}

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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/
int main() {
  ll n;
  cin >> n;
  vl a(n),b(n);
  REP(i,n){
    cin >> a[i];
    cin >> b[i];
  }
  ll ans = 0;
  RREP(i,n){
    ll ai = a[i]+ans;
    ll bi = b[i];
    ll d = ai/bi;
    if(ai%bi) d++;
    ans += bi*d-ai;
  }
  cout << ans<< endl;
  return 0;
}


Measured memory_bytes: 1920
/*
"Won't stop until I'm phenomenal."
- Phenomenal, Eminem
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define ff first
#define Shazam ios_base::sync_with_stdio(false);   cin.tie(NULL); cout.tie(NULL);
#define ss second
#define all(c) c.begin(),c.end()
#define endl "\n"
#define test() int t; cin>>t; while(t--)
#define fl(i,a,b) for(int i = a ; i <b ;i++)
#define get(a) fl(i,0,a.size())  cin>>a[i];
#define pra(a) fl(i,0,a.size()) cout<<a[i]<<" ";	cout<<endl;
#define pr(a,n) fl(i,0,n) cout<<a[i]<<" ";	cout<<endl;
const ll INF = 2e18;
const int inf = 2e9;
const int mod1 = 1e9 + 7;

vector<vector<int>> g;
map<pair<int,int>,int> mp;
int maxi;

void dfs(int u, int p, int pc){
    int id = 1;
    for(int v : g[u]){
        if(v==p) continue;
        if(pc==id) id++;
        mp[{min(u,v),max(v,u)}] = id;
        maxi = max(maxi,id);
        dfs(v,u,id);
        id++;
    }
}

int main(){
    Shazam;
    int n; cin>>n;
    g = vector<vector<int>>(n);
    vector<pair<int,int>> e;
    for(int i = 0 ; i < n-1; i++){
        int a, b; cin>>a>>b;
        a--;
        b--;
        e.push_back({min(a,b),max(a,b)});
        g[b].push_back(a);
        g[a].push_back(b);
        maxi = max(maxi,(int) g[a].size());
        maxi = max(maxi,(int) g[b].size());
    }
    dfs(0,0,0);
    cout<<maxi<<endl;
    for(auto p : e){
        cout<<mp[p]<<endl;
    }

    return 0;
}

Measured memory_bytes: 17032
#include <bits/stdc++.h>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,0,v.size()-1)cout << v[i] << " ";cout << endl;
#define arrprint(v,n) rep(i,0,n-1)cout << v[i] << " ";cout << endl;
#define matprint(v,n,m) rep(i,0,n-1){rep(j,0,m-1){cout << v[i][j] << " ";}cout << endl;}
using namespace std;
const int mod=1000000007;
const int INF=1001001001;
typedef long long ll;
typedef pair<int,int> P;

int main(){
    int n,m;
    cin >> n >> m;
    // if(m>n){puts("-1");return 0;}
    int ans = 0;
    bool flg = false;
    vector<int> c(n,-1);
    rep(i,0,m-1){
        int si, ci;
        cin >> si >> ci;
        si--;
        if(c[si] != -1){
            if(ci != c[si]){
                flg = true;
            }
        }
        c[si] = ci;
    }
    if(flg){
        puts("-1");
        return 0;
    }
    rep(i,0,n-1){
        if(c[i] != -1){
            ans += c[i]*pow(10,n-1-i);
        }
    }
    if(n>1 && c[0] == 0){
        puts("-1");
        return 0;
    }
    if(ans < pow(10,n-1) && n != 1)ans += pow(10,n-1);

    cout << ans << endl;
//  printf("%.10f\n",ans);

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#define PI 3.14159265
int main(void){
    double x=0,y=0,r=90.0;
    int t1,t2;
    for(;scanf("%d,%d",&t1,&t2),t1+t2;r-=t2){
        x+=t1*cos((r/180.0)*PI);
        y+=t1*sin((r/180.0)*PI);
    }
    printf("%d\n%d\n",(int)x,(int)y);
    return 0;
}

Measured memory_bytes: 1968
let rec find x uf =
  if uf.(x) < 0 then x else 
  let x' = find uf.(x) uf in
  uf.(x) <- x'; x'
let unite x y uf =
  let x, y = find x uf,find y uf in
  if x <> y then
    if uf.(x) < uf.(y) then ((
      uf.(x) <- uf.(x) + uf.(y);
      uf.(y) <- x
    )) else ((
      uf.(y) <- uf.(x) + uf.(y);
      uf.(x) <- y
    ))
let () =
  Scanf.scanf "%d %d" @@ fun n m ->
  let es = Array.init m (fun _ -> Scanf.scanf " %d %d" (fun x y -> x-1, y-1)) in
  let uf = Array.make n (-1) in
  Array.fold_right (fun (x, y) (v, stk) -> 
    let x, y = find x uf, find y uf in
    if x = y then (v, v::stk)
    else ((
      let xc, yc = uf.(x), uf.(y) in
      unite x y uf;
      (v - xc * yc, v::stk)
    ))) es (n*(n-1)/2, [])
  |> snd |> List.iter (Printf.printf "%d\n")
    


Measured memory_bytes: 10624
N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

x = 0 # values
y = 0 # costs
diff = x - y

for i in range(len(V)):
    if x + V[i] - (y + C[i]) > diff:
        diff = x + V[i] - (y + C[i])
        x = x + V[i]
        y = y + C[i]


print(diff)


Measured memory_bytes: 3060
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int a=scan.nextInt();
		int b=scan.nextInt();
		int c=scan.nextInt();
	if(a+b==c||b+c==a||a+c==b) {
		System.out.println("Yes");
	}
	else {
		System.out.println("No");
	}
	}
	}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll x,y; cin>>x>>y;
    int ans=0;
    while(x<=y){
        x<<=1;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
import math
S = str(input())
S=S[0:len(S)-1]

if len(S)%2!=0:
	S=S[0:len(S)-1]

for i in range (0, int(len(S)/2)):
	N = len(S)
	if S[0:int(N/2)] == S[int(N/2)::]:
		print(2*len(S[0:int(N/2)]))
		exit()	
	else:
		S=S[0:N-2]

Measured memory_bytes: 3064
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor
from bisect import bisect_left
setrecursionlimit(1000000)

INF = int(1e10)
MOD = int(1e9 + 7)

def input():
    return stdin.readline()[:-1]

def main():
    from builtins import int, map
    A, B, N = map(int, input().split())
    m = min(B - 1, N)
    ans = floor(A * m / B) - A * floor(m / B)
    print(ans)


if __name__ == '__main__':
    main()

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

int main(){
	int a, b;
	cin>> a >> b;
	for(int i = 1; i <= 3; ++i){
		if((a*b*i)&1){
			puts("Yes");
			return 0;
		}
	}
	puts("No");
	return 0;
}

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

using namespace std;

int main(){
    long long int x,ans;
    cin >> x;
    ans = x/11*2;
    if(x%11==0){
    }else if(x%11 < 7){
        ans++;
    }else{
        ans +=2;
    }
    cout << ans;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define oprecision    \
  cout.precision(30); \
  cerr.precision(7);
#define bb bool
#define ii int
#define ll long long
#define ff float
#define dd double
#define cc char
#define ss string
#define forn(sz) for (int i = 1; i <= sz; i++)
#define forni(i, sz) for (int i = 1; i <= sz; i++)
#define fornid(i, m, sz) for (int i = m; i <= sz; i++)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vii vector<ii>
#define vii64 vector<ll>
#define vb vector<bb>
#define F first
#define S second
#define int ll
using namespace std;
const int inf = 1000000000000000000;
int n, a[500], p[500], dp[500][500];
int rec(int l, int r) {
  if (l == r) return a[l];
  if (dp[l][r] != -1) return dp[l][r];
  int ans = inf;
  for (int i = l; i < r; i++) ans = min(rec(l, i) + rec(i + 1, r), ans);
  return dp[l][r] = ans + p[r] - p[l - 1];
}
main() {
  speed;
  oprecision;
  // code
  memset(dp, -1, sizeof dp);
  cin >> n;
  forn(n) cin >> a[i], p[i] = p[i - 1] + a[i];
  cout << rec(1, n) - p[n];
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

Measured memory_bytes: 2432
// <candy.cpp> - Sat Mar 25 16:58:17 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int MAXN=100010;
const int INF=1e9;
int a[MAXN];
bool cmp(int x,int y){return x>y;}
int main(){
    int n=gi();
    for(int i=1;i<=n;i++)a[i]=gi();
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
        if(i+1>a[i+1]){
            bool res=1;
            for(int j=i+1;a[j]==i;j++)res^=1;
            res&=(a[i]-i+1)&1;
            printf(res?"Second":"First");
            break;
        }
    return 0; 
}

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


#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T, class T2> void amax(T& a,T2 b){ if(a < b) a = b;}

int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int h, w;
	cin >>h >>w;
	vector<VI> ba(h, VI(w)), a(10, VI(10));
	rep(i, 10) rep(j, 10) cin >>a[i][j];
	rep(i, h) rep(j, w) cin >>ba[i][j];
	rep(k,10) rep(i,10) rep(j,10) a[i][j] =min(a[i][j], a[i][k] + a[k][j]);
	
	ll ans =0;
	rep(i, h) rep(j, w){
		if(ba[i][j] ==-1) continue;
		ans += a[ba[i][j]][1];
	}
	cout <<ans <<"\n";
	return 0;
}


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

using namespace std;

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

    // by salah el brens

    int n, m, ans = 0;
    cin >> n >> m;

    for (int i = 1; i * i <= m; i++)
        if (m % i == 0) {
            if (1ll * n * i <= m)
                ans = max(ans, i);
            if (1ll * n * (m / i) <= m)
                ans = max(ans, m / i);
        }

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[]agrs){
		Scanner sc=new Scanner(System.in);
		int w,h;
		while(sc.hasNextInt()){
		 h=sc.nextInt();
		 w=sc.nextInt();
		 if(w==0||h==0)break;
		 for(int i=0;i<h/2;i++){
			 for(int j=0;j<w/2;j++){
				 System.out.print("#.");
				 
				 }if(w%2==1)System.out.print("#");
				 System.out.println();
			 for(int j=0;j<w/2;j++){
				 System.out.print(".#");
				 } if(w%2==1)System.out.print(".");
                  System.out.println();
			 }if(h%2==1){
				 for(int j=0;j<w/2;j++){
					 System.out.print("#.");
					 
				 }
				 if(w%2==1)System.out.print("#");
				 System.out.println();
				 
		 }System.out.println();
			
		}
	}
}

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

int main()
{
	int count = 0;
	char  S[6];
	for(int i=0;i<6;i++) cin >> S[i];
	for (int i = 0; i < 6; i++) {
		if (S[i] == '1') ++count;
	}
	cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc=new Scanner(System.in);
        long a=sc.nextLong();
      	long b=sc.nextLong();
    	long c=gcd(a,b);
      long d=1;
      
      for(long i=2; i*i<=c;i++){
        if(c%i!=0) continue;
      	while(c%i==0){
        	c/=i;
        }
        d++;
      }
      if(c>1) d++;
      System.out.println(d);
        
    }
  	
  	private static long gcd(long a, long b){
    	while(a%b!=0){
        	long c=a%b;
          	a=b;
          	b=c;
        }
      return b;
    }
  
}

Measured memory_bytes: 21972
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<utility>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

#define MOD 1000000007;

int main(){
	int p, q, r;
	cin >> p >> q >> r;
	cout << p+q+r-max({p,q,r}) << endl;
	return 0;
}

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

#define LL long long
#define RG register

using namespace std;
template<class T> T gi() {
	T x = 0; bool f = 0; char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = 1, c = getchar();
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f ? -x : x;
}
const int N = 1e5 + 10;
int a[N], b[N], fa[N], p[N];
LL f[N], siz[N];
vector<int> e[N];
bool vis[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool cmp(int x, int y) { return a[x] < a[y]; }
int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	int n = gi<int>(), m = gi<int>();
	for (int i = 1; i <= n; i++) a[i] = gi<int>(), siz[i] = b[i] = gi<int>();
	for (int i = 1; i <= m; i++) {
		int x = gi<int>(), y = gi<int>();
		e[x].push_back(y), e[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) fa[i] = p[i] = i, a[i] = max(0, a[i] - b[i]);
	sort(p + 1, p + 1 + n, cmp);
	for (int i = 1; i <= n; i++) {
		int u = p[i]; vector<int> son; vis[u] = 1;		
		for (auto v : e[u]) {
			if (!vis[v] || u == find(v)) continue;
			son.push_back(find(v));
			siz[u] += siz[find(v)]; fa[find(v)] = u;
		}
		f[u] = siz[u] + a[u];
		for (auto v : son) f[u] = min(f[u], siz[u] - siz[v] + max(1ll * a[u], f[v]));
	}
	printf("%lld\n", f[p[n]]);
	return 0;
}


Measured memory_bytes: 9468
using System;

namespace ITP1_11_C
{
    class Dice : IEquatable<Dice>
    {
        private int top = 0, btm = 5, front = 1, back = 4, left = 3, right = 2;
        private int[] vals = new int[6];
        public int Top { get { return vals[top]; } }
        public int Btm { get { return vals[btm]; } }
        public int Front { get { return vals[front]; } }
        public int Back { get { return vals[back]; } }
        public int Left { get { return vals[left]; } }
        public int Right { get { return vals[right]; } }
        public Dice(int[] values)
        {
            Array.Copy(values, vals, 6);
        }
        public void W()
        {
            int tmp = left;
            left = top;
            top = right;
            right = btm;
            btm = tmp;
        }

        public void E()
        {
            int tmp = right;
            right = top;
            top = left;
            left = btm;
            btm = tmp;
        }

        public void C()
        {
            int tmp = front;
            front = right;
            right = back;
            back = left;
            left = tmp;
        }

        public bool Equals(Dice other)
        {
            var roll = "OCCCWCCCECCCECCCWCCCWCCC";
            foreach (var c in roll)
            {
                switch (c)
                {
                    case 'C':C(); break;
                    case 'W':W(); break;
                    case 'E':E(); break;
                    default: break;
                }
                if (Top == other.Top && Btm == other.Btm && Front == other.Front && Back == other.Back && Left == other.Left && Right == other.Right) return true;
            }

            return false;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Dice dice1 = new Dice(Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse));
            Dice dice2 = new Dice(Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse));
            Console.WriteLine(dice1.Equals(dice2) ? "Yes" : "No");
        }
    }
}

Measured memory_bytes: 8928
#include <cstdio>
#include <cstring>
#define MAXN 1000010
#define LL long long

int n;
char str[MAXN];
int nxt[MAXN];
int s[26][MAXN];
LL L,R,S,T;

void gaoNext(){
	nxt[1]=0;
	for(int i=2,j=1;i<=n;i++,j++){
		while(j && str[i]!=str[j]){
			if(j==1) j=0;
			else j=nxt[j-1]+1;
		}
		nxt[i]=j;
	}
}

void gaoS(){
	for(int i=0;i<26;i++){
		s[i][0]=0;
		for(int j=1;j<=n;j++)
			s[i][j]=s[i][j-1]+((str[j]=='a'+i)?1:0);
	}
}

void pre_gao(){
	gaoNext();
	int temp=n;
	while(temp*2>=n) temp=nxt[temp];
	n-=temp;
}

LL getS(int ch,LL len){
	if(len<=n) return s[ch][len];
	LL l1=T,l2=S;
	LL s1=s[ch][l1],s2=s[ch][l2];
	while(l1+l2<=len){
		LL l3=l1+l2,s3=s1+s2;
		l1=l2; l2=l3;
		s1=s2; s2=s3;
	}
	return s2+getS(ch,len-l2);
}

int main(){
#ifdef DEBUG
	freopen("F.in","r",stdin);
#endif
	scanf("%s",str+1);
	n=strlen(str+1);
	scanf("%lld%lld",&L,&R);
	pre_gao();
	gaoS();
	S=n; T=n-nxt[n];
	for(int i=0;i<26;i++)
		printf("%lld ",getS(i,R)-getS(i,L-1));
	return 0;
}


Measured memory_bytes: 78976
#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
    char s[100002];
    fgets(s, 100002, stdin);
    int l = strlen(s) - 1;
    s[l] = '\0';

    int k;
    scanf("%d", &k);

    for (int i = 0; i < l; ++i) {
        if (s[i] == 'a')
            continue;
        if ('z' - s[i] + 1 <= k) {
            k -= 'z' - s[i] + 1;
            s[i] = 'a';
        }
    }
    s[l - 1] += k % ('z' - 'a' + 1);

    printf("%s\n", s);

    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
 
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
 
const long long INF = 1e18;
//const ll mod = 1000000007;
ll N;
ll num[10010000];
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for(ll i = 1; i <= N; i++) {
        for(ll j = i; j <= N; j += i) {
            num[j]++;
        }
    }
    ll ans = 0;
    for(ll i = 1; i <= N; i++) {
        ans += i * num[i];
    }
    cout << ans << endl;
    return 0;
}

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


int N;

int main() {
    cin >> N;

    ll L_i = 2;
    ll L_j = 1;
    ll L;

    if (N == 1) cout << 1 << endl;

    else {
        for (int i=1;i<N;i++) {
            L = L_j + L_i;
            L_i = L_j;
            L_j = L;
        }
        cout << L << endl;
    }

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using uint = unsigned int;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;
const ld PI = acosl(-1);

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

    int N, Q;
    cin >> N;
    vector<int> cnt(100005);
    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        cnt[A]++;
        ans += A;
    }

    cin >> Q;
    for (int i = 0; i < Q; ++i) {
        int B, C;
        cin >> B >> C;
        ans += (ll)(C - B) * cnt[B];
        cnt[C] += cnt[B];
        cnt[B] = 0;
        cout << ans << '\n';
    }

    return 0;
}


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

using namespace std;
using ll = long long;

const long long inf = 1e9;
#define fr(i,a,n) for (int i=a;i<n;i++)
#define rfr(i,n,a) for (int i=n;i>=a;i--)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll> 
#define endl "\n"
typedef vector<int> VI;
typedef vector<ll> VL;
typedef priority_queue<int> Pqi;
typedef priority_queue<ll> Pql;

ll n, m, k;

int main () {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	n = 5;
	fr(i,1,n+1) {
		int x;
		cin >> x;
		if (x != i) {
			cout << i << endl;
			return 0;
		}
	}
	return 0; 
}


Measured memory_bytes: 3600
#include<bits/stdc++.h>
#define For(i,x,y) for (register int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (register int i=(x);i<(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fil(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef double db;
inline ll read(){
    ll x=0,f=1;char c=getchar();
    while ((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if (c=='-') f=-1,c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

namespace Geometry{
	const db eps = 1e-9;
	struct point{
		db x,y;
		inline point operator + (const point &p){return (point){x+p.x,y+p.y};}
		inline point operator - (const point &p){return (point){x-p.x,y-p.y};}
		inline db operator * (const point &p){return x*p.x+y*p.y;}
		inline point operator / (const db &v){return (point){x/v,y/v};}
		inline point operator * (const db &v){return (point){x*v,y*v};}
	};
	typedef point vec;
	inline db dot(vec a,vec b){return a.x*b.x+a.y*b.y;}
	inline db sqr(db x){return x*x;}
	inline db dis(point a,point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
	inline db dis2(point a,point b){return sqr(a.x-b.x)+sqr(a.y-b.y);}
	inline db cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
	struct line{
		point a,b;
	};
	inline point projection(point A,line b){
		point B=b.a,C=b.b;
		vec BA=A-B,BC=C-B,BD=BC*(BA*BC/dis2(B,C));
		return B+BD;
	}
	inline point reflection(point A,line b){
		point D=projection(A,b);
		return (point){D.x*2-A.x,D.y*2-A.y};
	}
	inline int Counter_Clockwise(point A,line b){
		point B=b.a,C=b.b;
		db f1=cross(C-B,A-B);
		if (fabs(f1)>eps) return (f1<0?2:1);
		db f2=(C-B)*(A-B);
		if (f2<0) return 3;
		return dis(B,C)<dis(A,B)?4:5;
	}
	inline int checkline(line a,line b){
		vec A=a.b-a.a,B=b.b-b.a;
		db f1=A*B;
		if (fabs(f1)<=eps) return 1;
		return dis(a.a,a.b)*dis(b.a,b.b)-fabs(f1)<=eps?2:0;
	}
	inline int checkseg(line a,line b){
		point A=a.a,B=a.b,C=b.a,D=b.b;
		if (max(A.x,B.x)<min(C.x,D.x)) return 0;
		if (min(A.x,B.x)>max(C.x,D.x)) return 0;
		if (max(A.y,B.y)<min(C.y,D.y)) return 0;
		if (min(A.y,B.y)>max(C.y,D.y)) return 0;
		db s=cross(B-A,C-A),h=cross(B-A,D-A);
		if (s*h>=eps) return 0;
		db i=cross(D-C,A-C),t=cross(D-C,B-C);
		return i*t<=eps;
	}
};
using namespace Geometry;

int main(){
//	freopen("data.in","r",stdin);
	int T;scanf("%d",&T);
	while (T--){
		line a;scanf("%lf%lf%lf%lf",&a.a.x,&a.a.y,&a.b.x,&a.b.y);
		line b;scanf("%lf%lf%lf%lf",&b.a.x,&b.a.y,&b.b.x,&b.b.y);
		printf("%d\n",checkseg(a,b));
	}
}


Measured memory_bytes: 3208
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <time.h>

using namespace std;
typedef long long ll;
#define pl pair<ll,ll>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); itr++)
#define dbg(x) cout << #x"="<< (x) << endl
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back(a) 
#define in(x) cin >> x;
#define all(x) (x).begin(), (x).end()
#define INF 2147483600
#define fi first
#define se second

int main(){
  int n;
  cin>>n;
  vector<int> c(n-1),s(n-1),f(n-1);
  rep(i,n-1){
    cin>>c[i]>>s[i]>>f[i];
  }
  ll ans=0;
  rep(i,n){
    if(i==n-1){
      cout<<0<<endl;
    }else{
      ans=0;
      // 出発
      FOR(j,i,n-1){
        if(ans>=s[j]){
          ans=ceil(double(1.0*(ans-s[j])/f[j]))*f[j]+s[j];
          ans+=c[j];
        }else{
          ans=s[j];
          ans+=c[j];
        }
      }
      cout<<ans<<endl;
    }

  }

  return 0;
}

Measured memory_bytes: 256
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    H, W, D = NMI()
    grid = [NLI() for i in range(H)]
    Q = NI()
    querys = [NLI() for i in range(Q)]

    point = [[-1,-1] for _ in range(H*W + 1)]
    for h in range(H):
        for w in range(W):
            a = grid[h][w]
            point[a] = [h, w]

    cost_S = [0] * (H*W + 1)
    for c in range(H*W + 1):
        if c <= D:
            continue

        cost_S[c] = cost_S[c-D] + abs(point[c][0] - point[c-D][0]) + abs(point[c][1] - point[c-D][1])

    for query in querys:
        l, r = query
        print(cost_S[r] - cost_S[l])


if __name__ == "__main__":
    main()

Measured memory_bytes: 42996
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        int[] a = new int[n];
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt()-1;
        }
        int[] time = new int[n];    //何回目のテレポで初めてその町に到達したかを示す 町番号は箱の番号+1
        time[0] = 0;    //今見たらこれいらなかったね
        int now = 0;    //今いる場所。forループの終わりで毎回更新する
        for(int i=1;;i++){      //2番目の条件がないので無限ループ式。確実にbreakできるとわかっている時以外はマネしないでね。iはステップ数。
            if(time[a[now]] != 0){  //0じゃなければ一度来たことがあるので、その場合...
                int loop = i - time[a[now]];    //ループ長は（現在のステップ数-前回この町に来た時に記録したステップ数）で表される
                k -= (k - i) / loop * loop;     //k回テレポートするのも、k - (k - i)/loop*loop回移動するのも結果は変わらないよね、ってことでkの値そのものを書き換えてしまう
                time = new int[n];  //到達履歴を消去してしまう（このあとループを考慮する必要がないため）
            }else {
                time[a[now]] = i;   //まだ来たことがなかった場合はtimeに何回目に来たことがあるかを記録するが、前のif文がtrueだとtimeを初期化している(2行前)のでその場合もこっちに来る。その場合この分を踏んでいる事には特に意味はない
            }
            now = a[now];
            if(i == k){     //k回「と同等のテレポート回数」(編集済み!!)のテレポートが終わったらbreakする。
                break;
            }
        }
        now++;
        System.out.println(now);    //そうすると素直にテレポートを繰り返した結果みたいな形で答えが出せるのです。
    }
}


Measured memory_bytes: 50124
// C - Scc Puzzle

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

int main() {
	ll N, M;
	cin >> N >> M;

	ll ans;
	if (N * 2 <= M) {
		// 'c'が余る場合
		ans = N;
		M = M - (N * 2); // 使われなかった'c'の数
		ans += (M / 4); // 'c'4つで'Scc'が一つ作れる
	} else {
		// 'S'が余る場合
		ans = M / 2; // 最初からあるcの数だけで決まる
	}

	cout << ans << endl;

	return 0;
}

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

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

// one-based numbering
struct UnionFind {
    vector<int> data;
    // i: (data[i] < 0) -> group size, (data[i] > 0) -> parent;
    UnionFind(int n) {
        data.resize(n+1, -1);
    }
    int find(int x) {
        if(data[x] < 0) return x;
        else return data[x] = find(data[x]);
    }
    int size(int x) {
        return -data[find(x)];
    }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if(x == y) return false;
        if (data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return true;
    }
    bool same(int x, int y) {
        x = find(x); y = find(y);
        return x == y;
    }
};

int main() {
    int n, m; cin >> n >> m;
    UnionFind uf(n);
    for (int i = 0; i < m; i++) {
        int x, y, z; cin >> x >> y >> z;
        uf.unite(x, y);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (uf.data[i] < 0) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF 1e9+7
#define rep(i,n) for(ll i=0;i<n;i++)
#define pii pair<int,int>
#define pll pair<ll,ll>
const int maxn = 1000000;
ll mod = INF;

int main(){
    int x;
    cin >> x;
    if(x==0)cout << 1<<endl;
    else cout << 0<<endl;
    return 0;
}

Measured memory_bytes: 3620
package main

import (
	"fmt"
)

func main() {

	var r, c int

	fmt.Scanf("%d%d", &r, &c)

	var rowcol [][]int

	for i := 0; i < r; i++ {

		var row []int

		for j := 0; j < c; j++ {
			var val int
			fmt.Scanf("%d", &val)

			row = append(row, val)
		}

		rowcol = append(rowcol, row)
	}

	for i := 0; i < r; i++ {

		colsum := 0

		for j := 0; j < c; j++ {
			fmt.Printf("%d ", rowcol[i][j])
			colsum += rowcol[i][j]
		}

		fmt.Println(colsum)

	}

	sum := 0

	for j := 0; j < c; j++ {
		rowsum := 0
		for i := 0; i < r; i++ {
			rowsum += rowcol[i][j]
		}

		sum += rowsum

		fmt.Printf("%d ", rowsum)
	}

	fmt.Println(sum)
}



Measured memory_bytes: 2040
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    n, m = map(int, readline().split())

    print((n - 1) * (m - 1))

    return


if __name__ == '__main__':
    main()


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

const long long MOD = 1e9+7;

int main() {
    string s;
    cin >> s;
    int len = (int)s.size();
    
    vector<vector<long long>> dp(len + 1, vector<long long>(4));
    dp.at(0).at(0) = 1;
    for (int i = 0; i < len; i++) {
        if (s.at(i) == '?') {
            for (int j = 0; j < 4; j++) {
                dp.at(i + 1).at(j) += dp.at(i).at(j) * 3 % MOD;
                dp.at(i + 1).at(j) %= MOD;
            }
            for (int j = 1; j < 4; j++) {
                dp.at(i + 1).at(j) += dp.at(i).at(j - 1);
            }
        }
        else {
            for (int j = 0; j < 4; j++) {
                dp.at(i + 1).at(j) += dp.at(i).at(j);
            }
            if (s.at(i) == 'A') dp.at(i + 1).at(1) += dp.at(i).at(0);
            else if (s.at(i) == 'B') dp.at(i + 1).at(2) += dp.at(i).at(1);
            else dp.at(i + 1).at(3) += dp.at(i).at(2);
        }

        for (int j = 0; j < 4; j++) {
            dp.at(i + 1).at(j) %= MOD;
        }
    }
    cout << dp.at(len).at(3) << endl;
}  

Measured memory_bytes: 7424