akhauriyash/Code-Regression huggingface dataset:
N,M,P=map(int,input().split())
A=[0 for i in range(M)]
B=[0 for i in range(M)]
C=[0 for i in range(M)]
G=[dict() for i in range(N)]
H=[dict() for i in range(N)]
for i in range(M):
    A[i],B[i],C[i]=map(int,input().split())
    G[B[i]-1][A[i]-1]=C[i]
    H[A[i]-1][B[i]-1]=C[i]
reached1=[0 for i in range(N)]
q=[N-1]
while(len(q)>0):
    r=q.pop()
    reached1[r]=1
    for p in G[r]:
        if reached1[p]==0:
            q.append(p)
reached2=[0 for i in range(N)]
q=[0]
while(len(q)>0):
    r=q.pop()
    reached2[r]=1
    for p in H[r]:
        if reached2[p]==0:
            q.append(p)
reached=[reached1[i]*reached2[i] for i in range(N)]
vertex_list=[]
vertex_num=[-1 for i in range(N)]
tmp=1
for i in range(N):
    if reached[i]==1:
        vertex_list.append(i+1)
        vertex_num[i]=tmp
        tmp+=1
num_v=len(vertex_list)
edges=[]
for i in range(M):
    if reached[A[i]-1]==1 and reached[B[i]-1]==1:
        edges.append((vertex_num[A[i]-1],vertex_num[B[i]-1],P-C[i]))
inf=10**10
dist=[inf for i in range(num_v)]
dist[0]=0
#print(reached)
#print(edges)
#print(vertex_list)
#print(vertex_num)
#辺の緩和
for i in range(num_v):
    for edge in edges:
        if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
            dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
            if i==num_v-1:
                print(-1)
                exit()
print(max(-dist[-1],0))


Measured memory_bytes: 53356
S = input()

firsthalf = int(S[:2])
lasthalf = int(S[2:])

if lasthalf <= 12 and lasthalf >= 1:
    if firsthalf > 12 or firsthalf == 0:
        ans = "YYMM"
    else:
        ans = "AMBIGUOUS"
else:
    if firsthalf == 0 or firsthalf > 12:
        ans = "NA"
    else:
        ans = "MMYY"

print(ans)

Measured memory_bytes: 2940
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        HashMap<Integer,Integer> hash = new HashMap<>();
        int[] a = new int[n];
        for (int i=0;i<n;i++){
            a[i] = sc.nextInt();
            if (hash.containsKey(a[i]))hash.put(a[i],hash.get(a[i])+1);
            else hash.put(a[i],1);
        }
        long ans = 0;
        for (int j:hash.values()){
            ans+=combination(j,2);
        }
        for (int i=0;i<n;i++){
            ans-=combination(hash.get(a[i]),2);
            ans+=combination(hash.get(a[i])-1,2);
            System.out.println(ans);
            ans+=combination(hash.get(a[i]),2);
            ans-=combination(hash.get(a[i])-1,2);
        }
    }
    static long factorial(long num){
        if (num<2)return 1;
        else return num*factorial(num-1);
    }
    static int arraySum(int[] array){
        int ans = 0;
        for (int value : array) ans += value;
        return ans;
    }
    static long combination(long a, long b){
        long data = 1;
        for (int i=0;i<b;i++){
            data*=a-i;
        }
        return data/factorial(b);
    }
    static double log(double base,double antilogarithm){
        return Math.log(antilogarithm)/Math.log(base);
    }

    static long gcd(long x,long y){
        if (y==0)return x;
        else return gcd(y,x%y);
    }
    static long lcm(long x,long y){
        return x/gcd(x,y)*y;
    }
    static HashMap<Long,Long> factorization(long num){
        HashMap<Long,Long> hash = new HashMap<>();
        long n = num;
        long count = 2;
        while (n>1){
            while (n%count==0){
                n/=count;
                if (hash.containsKey(count))hash.put(count,hash.get(count)+1);
                else hash.put(count,1L);
            }
            count++;
        }
        return hash;
    }

}


Measured memory_bytes: 72304
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
##############################

from collections import deque

N, M = map(int, input().split())
cost = [ [] for _ in range(N) ]
visited = [False] * N

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    cost[a].append(b)

#print(cost)

def bfs(node, dist):
    d = deque()
    d.append( (node, dist) )

    while d:
        (node, dist) = d.popleft()
        if visited[node] != False:
            continue

        visited[node] = dist

        for i in cost[node]:
            d.append((i, dist+1))

    return visited[-1]


if bfs(0, 0) == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Measured memory_bytes: 38148
#include<bits/stdc++.h>
#define rep(i,n) 				for(int i=0; i<(n); ++i)
#define all(c) 					(c).begin(),(c).end()
#define sortall(x)              sort(all(x))
#define tr(c,i) 				for( typeof( (c).begin() ) i = (c).begin();  i != (c).end(); ++i)
#define pb 						push_back
#define sz(a) 					int((a).size())
#define mp                      make_pair
#define ll                      long long
#define F                       first
#define S                       second
#define PI                      3.1415926535897932384626
// Input macros
#define s(n)                    scanf("%d",&n)
#define sc(n)                   scanf("%c",&n)
#define sl(n)                   scanf("%lld",&n)
#define sf(n)                   scanf("%lf",&n)
#define ss(n)                   scanf("%s",n)

// Others
#define test(t) 				int t; cin>>t; while(t--)
#define endl 					"\n"

using namespace std;

typedef pair<int, int> 			pii;
typedef pair<ll, ll> 	        pll;
typedef vector<int> 			vi;
typedef vector<ll>              vl;

 const int mod = 1e9+7;
// const int INF = 1e9+5;

const int nax = 1005;
char matrix[nax][nax];
int consta = 0;


int DFS( int i, int j, vector<vector<int>>& dp, int r, int c ){
	//cout<<"times : "<< ++consta <<endl;
	 if( i>=r || j>=c ){
		return 0;
	}
	
	if(dp[i][j]){
		//cout<<"dp return : "<<dp[i][j]<<endl;
		return dp[i][j];
	}
		
	if(matrix[i][j] == '#'){
		dp[i][j] = 0;
		return 0;
	}
		
	
	if( i == r-1 && j == c-1 ){
		dp[i][j] = 1;
		return 1;
	}
	
		
	int right = DFS(i+1, j, dp, r, c);
	int below = DFS(i, j+1, dp, r, c);
	
	dp[i][j] = (long)(right+below)%mod;
	return dp[i][j];
 }
	
	

int main(){
	
     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
     
     int r,c;
     scanf("%d%d",&r,&c);
     
     
     for(int i=0 ; i<r ; i++){
		scanf("%s",matrix[i]);
	 }
	 
	 
	 
	 vector<vector<int>> dp(r, vector<int>(c, 0));
	 
	 for(int i=r-1 ; i>=0 ; i--){
		 if(matrix[i][c-1] == '#'){
			 break;
		 }else{
			 dp[i][c-1] = 1;
		 }
	 }

	 for(int j=c-1 ; j>=0 ; --j){
		 if(matrix[r-1][j] == '#'){
			 break;
		 }else{
			 dp[r-1][j] = 1;
		 }
	 }
		
	//dp[r-1][c-1] = 0;
	
	 
	 for(int i=r-2 ; i>=0 ; --i){
		 for(int j=c-2 ; j>=0 ; --j){
			 if(matrix[i][j] == '.'){
				 dp[i][j] = (long)(dp[i+1][j] + dp[i][j+1])%mod;
			 }else{
				 dp[i][j] = 0;
			 }
		 }
	 }
	 
	 cout<<dp[0][0]<<endl;
	 
     return 0;

}
	

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

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = ReadArrayLong();
            var N = input[0];
            var K = input[1];
            if (K > (N - 1) * (N - 2) / 2)
            {
                Console.WriteLine(-1);
                return;
            }
            else
            {
                var ans = new List<int[]>();
                for (int i = 2; i <= N; i++)
                {
                    ans.Add(new int[] { 1, i });
                }
                var rem = (N - 1) * (N - 2) / 2 - K;
                for (int i = 2; i < N; i++)
                {
                    var end = false;
                    for (int j = i + 1; j <= N; j++)
                    {
                        if (rem == 0)
                        {
                            end = true;
                            break;
                        }
                        ans.Add(new int[] { i, j });
                        rem--;
                    }
                    if (end) break;
                }
                Console.WriteLine(ans.Count());
                foreach (var l in ans) Console.WriteLine(l[0] + " " + l[1]);
            }

            Console.WriteLine();
            Console.ReadLine();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

Measured memory_bytes: 13396
package main

import "fmt"
import "strconv"

func main() {
	var n, a, b int

	fmt.Scan(&n, &a, &b)

	var t int
	for i := 1; i <= n; i++ {
		s := strconv.Itoa(i)

		sum := 0
		for j := 0; j < len(s); j++ {
			var ci int
			c := string(s[j])
			ci, _ =  strconv.Atoi(c)
			sum += ci
		}

		if sum >= a && sum <= b {
			t += i
		}
	}

	fmt.Println(t)
}

Measured memory_bytes: 640
#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <list>
#include <cstring>
#include <stack>

using namespace std;

#define mod 1000000007

class UF
{
private:
	vector<int> root;

public:
	UF(int n)
	{
		root = vector<int>(n + 1, -1);
	}

	int getroot(int n)
	{
		if(root[n] == -1) return n;
		else return root[n] = getroot(root[n]);
	}

	void add(int x, int y)
	{
		x = getroot(x);
		y = getroot(y);
		if(x == y) return;
		if(x > y) swap(x, y);
		root[y] = x;
		return;
	}
};

int main()
{
	int n, m;
	cin >> n >> m;
	UF uf(n);
	for(int i = 0; i < m; i++){
		int s, t;
		cin >> s >> t;
		uf.add(s, t);
	}
	int q;
	cin >> q;
	for(int i = 0; i < q; i++){
		int s, t;
		cin >> s >> t;
		if(uf.getroot(s) == uf.getroot(t)) cout << "yes" << endl;
		else cout << "no" << endl;
	}
	return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//

int main() {
    init();
    string S;
    cin >> S;
    ll sn = S.size();

    stack<ll> st;
    vl ans, A(sn), AI(sn);
    rep(i, sn){
        if (S[i] == '\\')
            st.emplace(i);
        else if(S[i] == '/'){
            if (st.empty()) continue;
            ll si = st.top();
            st.pop();

            A[si] = i - si, AI[si] = i;
        }
    }

    ll ai = 0;
    while(ai<sn){
        while (ai<sn and AI[ai] == 0) ai++;
        if (ai == sn) break;

        ans.eb(accumulate(A.begin() + ai, A.begin() + AI[ai], 0ll));
        ai = AI[ai];
    }

    cout << accumulate(all(ans), 0ll) << endl;
    cout << ans.size();
    rep(i, ans.size()) cout << " " << ans[i];
    cout << endl;
}


Measured memory_bytes: 3392
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <numeric>
using namespace std;

int x,y;
int main(void)
{
	cin>>x>>y;
	int max=0;
	for(int i=min(x,y);i>0;i--){
		if(x%i==0&&y%i==0){
			max=i;
			break;
		}
	} 
	cout<<x+1+y-max<<endl;


	return 0;
}


Measured memory_bytes: 3136
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    ll n, m;

    cin >> n >> m;

    set<ll> s;

    ll a = 1, b = n;

    for (ll i = 0; i < m; i++)
    {
        if (s.find(abs(b - a)) != s.end() || s.find(abs(n + a - b)) != s.end() || abs(b - a) == abs(n + a - b))
        {
            b--;
        }

        cout << a << " " << b << endl;
        s.insert(abs(b - a));
        s.insert(abs(n + a - b));

        a++;
        b--;
    }
}


Measured memory_bytes: 11904
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(s: str, K: int):
    N = len(s)
    for i in range(ord('a'), ord('z')+1):
        c = chr(i)
        l = -1
        subs = []
        while c in s[l+1:]:
            l = s.index(c, l+1)
            for r in range(l+1, min(N+1, l+1+K)):
                subs.append(s[l:r])
        subs = sorted(list(set(subs)))
        if len(subs) > K-1:
            break
        else:
            K -= len(subs)
            continue
    print(subs[K-1])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    K = int(next(tokens))  # type: int
    solve(s, K)


if __name__ == '__main__':
    main()


Measured memory_bytes: 4324
#include<bits/stdc++.h>
#include<vector>
#include<deque>
#include<list>
#define rep(i,n) for(ll i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=100000000000000001;
struct edge{int to,cost;};
struct pos{
	int x,y,cost;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};


int main() {

	int a,b;
	int k;
	cin>>k;
	cin>>a>>b;

	for(int i=a; i<=b; i++){
		if(i%k==0){
			cout<<"OK"<<endl;
			return 0;
		}
	}
	cout<<"NG"<<endl;

	return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define ll          long long int
#define uu          first
#define vv          second
#define pii         pair<int,int>
#define pll         pair<ll,ll>
#define tp          tuple<int,int,int>
#define fastio      ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
const int INF = 1e9;
const ll MOD = 998244353;

const int N = 1e6 + 6;

int main()  {
    fastio;
    ll n , x , m;
    cin>>n>>x>>m;
    vector<ll>vals , rec(m, -1), cyc;

    for(int i =0 ; rec[x] == -1; i++) {
        vals.push_back(x);
        rec[x] = i;
        x = (x*x)%m;
    }


    int id = rec[x];

    // for(auto x : vals) cout<<x<<" ";
    // cout<<'\n';

    if(n < id) {
        ll tot = 0;
        for(int i =0 ; i < n ; i++ ) tot += vals[i];
        cout<<tot<<'\n';
        return 0;
    }

    ll tot1 = 0 , tot2 = 0;
    for(int i =0 ; i < id ; i++ ) tot1 += vals[i] ;
    



    for(int i =id ; i < vals.size() ; i++ ) cyc.push_back(vals[i]);
    for(auto x : cyc) tot2 += x ;

    // cout<<tot1<<" "<<tot2<<'\n';

    n -= id;

    // cout<<n<<" "<<id<<'\n';

    ll times = n / cyc.size();
    int rem = n % cyc.size();

    ll ans = tot1;

    ans += times * tot2 ;

    for(int i =0 ; i < rem ; i++ ) ans += cyc[i];
    cout<<ans<<'\n';
    return 0;





}

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

int main()
{
  int n, m;
  cin >> n >> m;
  vector<int> num(n);

  rep(i, n) num[i] = -1;
  vector<int> s(m);
  vector<int> c(m);
  rep(i, m)
  {
    cin >> s[i] >> c[i];
    s[i]--;
  }
  rep(i, m)
  {
    if (num[s[i]] != -1 && num[s[i]] != c[i])
    {
      cout << -1 << endl;
      return 0;
    }
    num[s[i]] = c[i];
  }
  if (n > 1 && num[0] == -1)
    num[0] = 1;
  if (n > 1 && num[0] == 0)
  {
    cout << -1 << endl;
    return 0;
  }
  rep(i, n) cout << (num[i] == -1? 0: num[i]);
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
#define ll long long
using namespace std;

int main(){
    ll n,k;
    cin>>n>>k;
    vector<ll> data1; 
    vector<ll> data2;
    for (ll i=0; i<k; i++){
        ll a,b;
        cin>>a>>b;
        data1.push_back(a);
        data2.push_back(b);
    }
    sort(data1.begin(), data1.end());
    sort(data2.begin(), data2.end());
    ll p=data1.back();
    ll q=data2[0];
    if (p>q) cout<<"0"<<endl;
    else cout<<q-p+1<<endl;
}

Measured memory_bytes: 2036
#include <stdio.h>
#include <math.h>

#define M_PI 3.141592653589793

int main(void) {

	int i, n;
	int num[100];

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		scanf("%d", &num[i]);
	}
	for (i = n - 1; i > 0; i--) {
		printf("%d ", num[i]);
	}
	printf("%d\n", num[0]);



	return 0;

}

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

int main() {
	int n,p,q,r,s,i, j,k,
		box1[3][10] = {},
		box2[3][10] = {},
		box3[3][10] = {},
		box4[3][10] = {};
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> p>>q>>r>>s;
		if (p == 1) {
				box1[q - 1][r - 1] += s;
			}
		if (p == 2) {
				box2[q - 1][r - 1] += s;
		}
		if (p == 3) {
			box3[q - 1][r - 1] += s;
		}
		if (p == 4) {
			box4[q - 1][r - 1] += s;
		}
	}
	for (j = 0; j < 3; j++) {
		for (k = 0; k < 10; k++) {
			cout << " " << box1[j][k];
		}
		cout << "\n";
	}
	cout << "####################\n";
	for (j = 0; j < 3; j++) {
		for (k = 0; k < 10; k++) {
			cout << " " << box2[j][k];
		}
		cout << "\n";
	}
	cout << "####################\n";
	for (j = 0; j < 3; j++) {
		for (k = 0; k < 10; k++) {
			cout << " " << box3[j][k] ;
		}
		cout << "\n";
	}
	cout<< "####################\n";
	for (j = 0; j < 3; j++) {
		for (k = 0; k < 10; k++) {
			cout << " " << box4[j][k] ;
		}
		cout << "\n";
	}
	
	return 0;
}


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

using ll =  long long;
using pint =  pair<int,int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vpint = vector<pint>;

#define repi(i,start,end) for(int (i)=(start),TemPNuM=(int)(end);(i)<TemPNuM;++(i))
#define rep(i,end) repi((i),0,(end))
#define rfor(x,v) for(auto& (x) : (v))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fsort(v,lambda) sort(all((v)),(lambda))
#define vin(v) rep(i,(v).size())cin >> (v)[i];
#define vpin(v) rep(i,(v).size())cin>>v[i].first>>v[i].second
#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T>void println(T a){if(cout.precision()!=12)cout<<setprecision(12);cout<<a<<endl;}
//lambda: [](int x, int y){return x<y;}


signed main(void){
    int n,r;cin>>n>>r;
    if(n>=10){
        cout << r << endl;
    }else{
        cout << r + 100*(10-n) << endl;
    }

    return 0;
}


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

typedef long long ll;
typedef pair<int, int> P;

const ll mod = 1000000007;
const int inf = 1e9;
const long long INF = 1LL << 60;   // INFの値は1152921504606846976


int main()
{
    int n;
    cin >> n;
    int a,b;
    cin >> a >> b;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        string s = to_string(i);
        int cnt = 0;
        for(int i = 0; i < s.size(); i++){
            cnt += (s[i]-'0');
        }
        if(a <= cnt && cnt <= b) ans += i;
    }
    cout << ans;
}

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

#define CEIL(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))
#define X first
#define Y second

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vl = vector<ll>;
using vs = vector<string>;

constexpr int MOD = int(1e9 + 7);
constexpr int INF = int(1e9 + 1);
constexpr ll LLINF = ll(4 * 1e18 + 1);
// constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(10);
	string s;
	cin >> s;
	int n = s.size();
	if(s[0] == '0' || s[n - 1] == '1'){
		cout << "-1\n";
		return 0;
	}
	for(int i = 0; i < n / 2; ++i){
		if(s[i] != s[n - i - 2]){
			cout << "-1\n";
			return 0;
		}
	}
	cout << "1 2\n";
	int b = 2, c = 3;
	for(int i = 1; i < n - 1; ++i){
		cout << b << " " << c << "\n";
		if(s[i] == '0'){
			c++;
		}
		else{
			b = c;
			c++;
		}
	}
	
	return 0;
}


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

const int MAX_N = 50;

int main(){
	int n,m,c;
	cin>>n>>m;
	int a[MAX_N*2],ans[MAX_N]={0};
	for (int i = 0; i < m*2; i++){
		cin>>c;
		ans[c]++;
	}

	for (int i = 1; i <= n; i++){
		cout<<ans[i]<<endl;
	}


}


Measured memory_bytes: 256
if __name__ == "__main__":
    s = input()

    tmp = set(s)

    if 'N' in tmp:
        if 'S' not in tmp:
            print('No')
            exit()

    if 'S' in tmp:
        if 'N' not in tmp:
            print('No')
            exit()

    if 'E' in tmp:
        if 'W' not in tmp:
            print('No')
            exit()

    if 'W' in tmp:
        if 'E' not in tmp:
            print('No')
            exit()

    print('Yes')


Measured memory_bytes: 3060
#include <stdio.h>
 
int main() {
    int n, i, j, a[100][100], b, m, c;
    scanf("%d", &n);
     
    for ( i = 0; i < n; i++ ) {
        for ( j = 0; j < n; j++ ) {
            a[i][j]  = 0;
        }
    }
     
    for ( i = 0; i < n; i++) {
        scanf("%d %d", &b, &m);
        for ( j = 0; j < m; j++ ) {
            scanf("%d", &c);
            a[b-1][c-1]  = 1;
        }
    }
     
     
    for ( i = 0; i < n; i++ ) {
        for ( j = 0; j < n; j++) {
            printf("%d", a[i][j]);
            if ( j != n-1 ) 
               printf(" ");
             
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 1820
//Name: Shopping in JOI Kingdom
//Level: 3
//Category: グラフ,Graph,最短経路
//Note:

/*
 * とりあえず道の途中に家があるときのことは考えず，各頂点についてショッピングモールからの
 * 最短距離を求める．
 * これは各ショッピングモールを始点としたダイクストラで求められる．
 * ただしナイーブにやると最大ケースで死にそうなので，ダイクストラの途中で他のショッピングモールに
 * ぶつかった場合はそこで枝刈りするようにした．
 *
 * ある2頂点があって，それぞれのショッピングモールへの最短距離がaとbで距離lの辺でつながっているとき，
 * この辺上での最遠点では
 * a+ul == b+(1-u)l
 * が成立しているはずであるから，各aとbの組について方程式を解いてulを求め，最大のa+ulを選べばそれが解となる．
 * (最短距離の定義より，min(a,b)+l >= max(a,b)であることに注意)
 */
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

struct Road {
    int from, to;
    int len;

    Road() {}
    Road(int f, int t, int l) : from(f), to(t), len(l) {}
};

vector<Road> roads_of[3000];
bool is_shopping_mall[3000];
int min_dist[3000];

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

    int N, M, K;
    cin >> N >> M >> K;
    for(int i = 0; i < M; ++i) {
        int a, b, l;
        cin >> a >> b >> l;
        --a; --b;
        roads_of[a].push_back(Road(a, b, l));
        roads_of[b].push_back(Road(b, a, l));
    }
    fill_n(is_shopping_mall, N, false);
    for(int i = 0; i < K; ++i) {
        int a;
        cin >> a;
        --a;
        is_shopping_mall[a] = true;
    }
    fill_n(min_dist, N, INT_MAX);

    static int memo[3000];
    for(int start = 0; start < N; ++start) {
        if(!is_shopping_mall[start]) continue;
        fill_n(memo, N, INT_MAX);
        priority_queue<pair<int, int> > q;
        q.push(make_pair(0, start));
        memo[start] = 0;
        while(!q.empty()) {
            int cost = -q.top().first;
            int pos = q.top().second;
            q.pop();
            if(memo[pos] < cost) continue;
            min_dist[pos] = min(min_dist[pos], cost);

            for(vector<Road>::iterator it = roads_of[pos].begin(); it != roads_of[pos].end(); ++it) {
                if(is_shopping_mall[it->to]) continue;

                int nc = cost + it->len;
                if(memo[it->to] > nc) {
                    memo[it->to] = nc;
                    q.push(make_pair(-nc, it->to));
                }
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < N; ++i) {
        int d = 0;
        const int a = min_dist[i];
        // a+ul == b+vl, u+v == 1
        // a+ul == b+(1-u)l
        // 2ul == b-a+l
        // ul == (b-a+l)/2
        for(vector<Road>::iterator it = roads_of[i].begin(); it != roads_of[i].end(); ++it) {
            const int b = min_dist[it->to];
            if(b >= a) {
                int ul = (b-a+it->len) / 2;
                if((b-a+it->len) % 2 == 1) ++ul;
                d = max(d, min_dist[i] + ul);
            }
        }
        ans = max(ans, d);
    }

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

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

using namespace std;

int main() {
    int n, y; cin >> n >> y;
    y /= 1000;
    for (int i = 0; i <= y / 10 && i <= n; i++) {
        for (int j = 0; j <= (y - 10 * i) / 5 && j <= n - i; j++) {
            if (y - 10 * i - 5 * j == n - i - j) {
                cout << i << " " << j << " " << n - i - j << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;
    return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;
import static java.lang.System.out;

public class Main {
    static MyReader in = new MyReader();

    public static void main(String[] args) {
        int N = in.i();
        long K = in.l();
        int[] A = in.ii(N);
        for (int i = 0; i < N; i++) {
            A[i]--;
        }
        int ans = solve(N, K, A);
        out.println(ans);
    }

    static  int solve(int N, long K, int[] A) {
        int[] tel = new int[N + 1];
        int[] path = new int[N];
        Arrays.fill(path, -1);
        path[0] = 0;
        int i = 1;
        int v = 0;
        while (true) {
            tel[i] = v = A[v];
            if (path[v] > -1) {
                break;
            }
            path[v] = i++;
        }
        int pref = path[v];
        int loop = i - path[v];
        int ans = tel[(int)(Math.max(0, K - pref) % loop + Math.min(K, pref))] + 1;
        return ans;
    }
}

class MyReader extends BufferedReader {
    char[] cbuf = new char[1024];
    int head = 0;
    int tail = 0;

    MyReader() {
        super(new InputStreamReader(System.in));
    }

    char next() {
        if (head == tail) {
            try {
                tail = read(cbuf, 0, cbuf.length);
            } catch (IOException e) {}
            head = 0;
        }
        return cbuf[head++];
    }

    void back() {
        head--;
    }

    boolean minus() {
        boolean minus;
        while (true) {
            char c = next();
            if (c != ' ' && c != '\n' && c != '\r') {
                if (!(minus = c == '-')) back();
                return minus;
            }
        }
    }

    void skip() {
        while (true) {
            char c = next();
            if (c != ' ' && c != '\n' && c != '\r') {
                back();
                break;
            }
        }
    }

    char[] s(final int N) {
        skip();
        char[] s = new char[N];
        for (int i = 0; i < s.length; i++) {
            s[i] = next();
        }
        return s;
    }

    int i() {
        boolean minus = minus();
        int n = 0;
        while (true) {
            int k = next() - '0';
            if (k < 0 || 9 < k) break;
            n = 10 * n + k;
        }
        return minus ? -n : n;
    }

    int[] ii(final int N) {
        int[] a = new int[N];
        for (int j = 0; j < a.length; j++) a[j] = i();
        return a;
    }

    long l() {
        boolean minus = minus();
        long n = 0;
        while (true) {
            int k = next() - '0';
            if (k < 0 || 9 < k) break;
            n = 10 * n + k;
        }
        return minus ? -n : n;
    }
}


Measured memory_bytes: 37920
/*{{{*/
#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 r,D,x;
  cin >> r>> D>> x;
  REP(i,10){
    x = r*x-D;
    cout << x<< endl;
  }
  return 0;
}

Measured memory_bytes: 256
// atcoder/abc050/A/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int a, b;
  char c;
  while (cin >> a >> c >> b) {
    if (c == '-') cout << a - b << endl;
    else cout << a + b << endl;
  }

  return 0;
}


Measured memory_bytes: 256
import java.util.*;
import javax.lang.model.util.ElementScanner6;
import java.lang.Math;

public class Main {

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

        // 入力
        int h1 = sc.nextInt();
        int m1 = sc.nextInt();
        int h2 = sc.nextInt();
        int m2 = sc.nextInt();
        int k = sc.nextInt();
        //String s = sc.next();

        // 処理
        //int out = 0;
        int times = (h2 * 60 + m2) - (h1 * 60 + m1);
        int out = times - k;
        if (out < 0){
            out = 0;
        }

        // 出力
        System.out.println(out);
    }    
}


Measured memory_bytes: 35720
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
using namespace std;

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

int n;
int r[100], c[100];
int dp[100][100];
const int INF = 1000000000;

int main() {
  cin >> n;
  rep(i, n) {
    cin >> r[i] >> c[i]; 
  }
  rep(i, 100) {
    rep(j, 100) {
      if(i == j) dp[i][j] = 0;
      else dp[i][j] = INF;
    }
  }

  for(int w = 1; w < n; w++) {
    for(int i = 0; i + w < n; i++) {
      int j = i + w;
      for(int k = 0; k < j; k++) {
        int num_prod = r[i] * c[k] * c[j];
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + num_prod);
      }
    }
  }

  cout << dp[0][n-1] << endl;
  return 0;
}


Measured memory_bytes: 3120
import sys



n,m,x=map(int,input().split())

a=[]

s=[0]*m

money=0

for i in range(n):
  A=list(map(int,input().split()))
  a.append(A)

  money+=A[0]

  for j in range(1,m+1):
    s[j-1]+=A[j]

for i in range(m):
  if s[i]<x:
    print("-1")
    sys.exit()




buy=[0]*n

saitei=-1

for i in range(1,(2**n)+1): #全組み合わせ
  buy=[0]*n
  t=[0]*m
  money=0
  i1=i
  for j in range(n): #どれを買うか
    buy[j]=(i1)%2
    i1=int((i1)/2)

    if buy[j]==1:
      money+=a[j][0]
      for k in range(1,m+1): #買った本no達成度の総和
        t[k-1]+=a[j][k]
  #print(buy)
  #print(t)
  flag=True
  for r in range(m):
    if t[r]<x:
      flag=False
      break
  if flag==True:
    if saitei==-1 or saitei>money:
      saitei=money

print(saitei)


Measured memory_bytes: 68852
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <queue>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#define ll long long
#define fr(i,k,N) for(decltype(N+k) i=k; i<N;i++)
#define rep(i,N) for(decltype(N) i=0; i<N;i++)
#define ALL(v) v.begin(),v.end()
using namespace std;
template <class X> void pr(X test){cout<<test<<endl;}
template <class X> void prr(X test){for(auto it:test){cout<<it<<endl;}}
template <class X> void prrr(X test){int f=0;for(auto it:test){cout<<(f++!=0?" ":"")<<it;}cout<<endl;}
template<typename X>
istream&operator>>(istream&i,vector<X>&v){for(X&x:v)i>>x;return i;}

class UF { // union find from https://github.com/kartikkukreja/blog-codes (MIT)
    // [usage]
    // auto uf = new UF(n);
    // uf->merge(l, r); // 0 <= l, r <= n-1
    // ...
public:
    int *id; // inner id
    int cnt; // number of all vartices
    int *sz; // sz[i] means size of i's set
    UF(int N)   {
        cnt = N;
        id = new int[N];
        sz = new int[N];
        for(int i=0; i<N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }
    ~UF() {
        delete [] id;
        delete [] sz;
    }
    int find(int p) {
        int root = p;
        while (root != id[root]) root = id[root];
        while (p != root) {
            int newp = id[p];
            id[p] = root;
            p = newp;
        }
        return root;
    }
    void merge(int x, int y) {
        int i = find(x);
        int j = find(y);
        if (i == j) return;
        
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        } else {
            id[j] = i;
            sz[i] += sz[j];
        }
        cnt--;
    }
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
    int count() {
        return cnt;
    }
};

// return 約数unordered_set 1 <= x <= n
auto divv = [](auto n) {
  unordered_set<decltype(n)> v;
  for(decltype(n) i = 1; i*i <= n; i++) {
    if(n%i == 0) {
      v.insert(i);
      if(i*i != n) v.insert(n/i);
    }
  }
  return v;
};

// check prime (and n>=2) or not
auto isPrime = [](auto n){
  if(n <= 1) return false;
  for(decltype(n) i = 2; i <= sqrt(n); ++i) {
      if(n % i == 0) {
          return false;
      }
  }
  return true;
};



int main() {
    ll n;
    cin>>n;
    auto v = divv(n);
    ll i = 2*n;
    for(auto it: v){
        i = min (i, it + n/it);
    }
    pr(i-2);
}


Measured memory_bytes: 512
using System;
using System.Text;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Threading.Tasks;

class Solve
{
	const int mod = 1000000007;
	static void Main(string[] args)
	{
		var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
		int a = input[0];
		int b = input[1];
		int c = input[2];

		string ans = "NO";
		for(int i = 1; i <= b; i++)
		{
			if ((a * i) % b == c)
			{
				ans = "YES";
				break;
			}
		}
		Console.WriteLine(ans);
	}
}

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

bool isSmallAlphabet(char& ch) {
  /* a ~ z(ascii) : 97 ~ 122 */
  if('a' <= ch && ch <= 'z') return true;
  else return false;
}

bool isHit(string& str) {
  if(str.find("the") != str.npos) return true;
  else if(str.find("this") != str.npos) return true;
  else if(str.find("that") != str.npos) return true;
  else return false;
}

/* ????????¶??????????§£??? */
void CaesarCipher(string& _str) {
  
  /* parameter??????????????¢??????????????????????????????????????? */
  for(int parameter = 0; parameter < 26; ++parameter) {
    string str = _str;
    for(int i = 0; i < (int)str.length(); ++i) {
      
      /* ?°?????????¢??????????????????????????? */
      if(isSmallAlphabet(str[i])) {
        str[i] += parameter;
        /* ???????????????????°?????????§???????????£??????*/
        if(!isSmallAlphabet(str[i])) {
          str[i] -= 26;
        }
      }

    }

    /* Find "the" or "this" or "that" */
    if(isHit(str)) {
      cout << str << endl;
    }
  }
}

int main() {
  string str;
  while(getline(cin, str)) {
    CaesarCipher(str);
  }
  return 0;
}

Measured memory_bytes: 3112
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int d[100];
int m;

int main()
{
  int i = 0;
  int dd;
  while(cin >> dd)
  {
    d[dd]++;
    m = max(m, d[dd]);
    i++;
  }
  for(int i = 0; i < 100; i++)
  {
    if(m == d[i])
      cout << i << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
from collections import deque
S=input()
Q=int(input())
q=deque(list(S))
directed=True
for i in range(Q):
    command=input().split()
    if command[0]=="1":
        directed=not(directed)
    else:
        if (command[1]=="1")==directed:
            q.appendleft(command[2])
        else:
            q.append(command[2])
ans=""
while(len(q)>0):
    if directed:
        t=q.popleft()
        ans+=t
    else:
        t=q.pop()
        ans+=t
print(ans)


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

int main() {
  int W, H, N;
  cin >> W >> H >> N;
  vector<int> x(N), y(N), a(N);
  for (int i = 0; i < N; i++) {
    cin >> x.at(i) >> y.at(i) >> a.at(i);
  }
  
  int x_min = 0, x_max = W, y_min = 0, y_max = H;
  
  for (int i = 0; i < N; i++) {
    if (a.at(i) == 1) {
      x_min = max(x_min, x.at(i));
    } else if (a.at(i) == 2) {
      x_max = min(x_max, x.at(i));
    } else if (a.at(i) == 3) {
      y_min = max(y_min, y.at(i));
    } else if (a.at(i) == 4) {
      y_max = min(y_max, y.at(i));
    }
  }
  
  if ((x_min < x_max) and (y_min < y_max)) {
    cout << (x_max - x_min) * (y_max - y_min) << endl;
  } else {
    cout << 0 << endl;
  }
}


Measured memory_bytes: 3604
a, b, c, x, y = map(int,input().split())

if x==y:
    ans = min(x*a+y*b, 2*x*c)
elif x>y:
    ans = min(x*a+y*b, 2*x*c, (x-y)*a+2*y*c)
else:
    ans = min(x*a+y*b, 2*y*c, (y-x)*b+2*x*c)

print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define lln long long int
#define llu unsigned lln
#define sc(n) scanf("%d",&n);
#define scl(n) scanf("%lld",&n);
#define scd(n) scanf("%lf",&n);
#define pf(res) printf("%d\n",res);
#define pfl(res) printf("%lld\n",res);
#define pfd(res) printf("%lf\n",res);
#define maxii 100005
using namespace std;
typedef pair<int,int> pii;
typedef pair<lln,lln> pll;
typedef vector<int> vi;
typedef vector<lln> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;


int arr[maxii];
int arr2[maxii];
int gcd(int a,int b)
{
    if(b==0){
      return a;
     }
    return gcd(b,a%b);
}
int lcm(int a,int b)
{
    int res=(a*b)/gcd(a,b);
    return res;
}
int po(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b%2!=0)
        {
            res*=a;
            b--;
        }
        else
        {
            a*=a;
            b/=2;
        }
    }
    return res;
}

lln modMul(lln  a, lln b,lln mod){
    lln ans = 0;
    a = a % mod;
    while (b > 0){
        if ( b % 2 )ans = (ans%mod+ a%mod) % mod;
        a = (a%mod * 2%mod) % mod;
        b /= 2;
    }
    return ans % mod;
}
lln powerMod(lln a,lln b,lln mod){
	if(b==0)return 1LL%mod;
	lln x=powerMod( a,b/2,mod );
	x = ( x%mod * x%mod ) % mod;
	if( b%2==1 )x = ( x%mod * a%mod ) % mod;
	return x%mod;
}

int main()
{
   int w,a,b;
   cin>>w>>a>>b;
   if(a==b)cout<<0;
   else if(a<b)
   {
       if(a+w>=b)cout<<0;

       else
       {
           cout<<b-a-w;
       }
   }
   else if(b<a)
   {
       if(b+w>=a)cout<<0;
       else
       {
           cout<<a-b-w;
       }

   }
}



Measured memory_bytes: 3580
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
    typedef long long ll;
    #define double long double
    const int INF=0x3f3f3f3f;
    const ll LLINF=0x3f3f3f3f3f3f3f3fll;
    ll qread()
    {
        ll ans=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
        while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
        return ans*f;
    }
    void write(ll num)
    {
        if(num<0) {num=-num;putchar('-');}
        if(num>9) write(num/10);
        putchar('0'+num%10);
    }
    void write1(ll num){write(num);putchar(' ');}
    void write2(ll num){write(num);puts("");}
    #define FR first
    #define SE second
    #define MP make_pair
    #define pr pair<int,int>
    #define PB push_back
    #define vc vector
    void chmax(ll &x,const ll y) {x=x>y?x:y;}
    void chmin(ll &x,const ll y) {x=x<y?x:y;}
    const int MAX_N=1e5+10;
    const ll MOD=998244353;
	
	ll b[MAX_N];int c[MAX_N];
	vc<int> son[MAX_N];
	ll g[MAX_N];
	void dp(int x)
	{
		if(son[x].size())
		{
			for(int t=0;t<(int)son[x].size();t++) dp(son[x][t]),b[x]+=b[son[x][t]];
			g[x]=LLINF;
			for(int t=0;t<(int)son[x].size();t++)
			{
				int y=son[x][t];
				chmin(g[x], max(g[y],(ll)c[x])+(b[x]-b[y]) );
			}
		}
		else g[x]=b[x]+c[x];
	}
	int pos[MAX_N];bool cmp(int x,int y){return c[x]<c[y];}
	vc<int> to[MAX_N];
	int fa[MAX_N];int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);}
    void main()
    {
		int n=qread(),m=qread();for(int i=1;i<=n;i++) c[i]=qread(),b[i]=qread(),c[i]=max(int(c[i]-b[i]),0);
		for(int i=1;i<=n;i++) pos[i]=i;sort(pos+1,pos+n+1,cmp);
		for(int i=1;i<=m;i++){int x=qread(),y=qread();to[x].PB(y);to[y].PB(x);}
		for(int i=1;i<=n;i++)
		{
			int x=pos[i];fa[x]=x;
			for(int t=0;t<(int)to[x].size();t++)
			{
				int y=to[x][t],tt=findfa(y);
				if(fa[y]!=0 and tt!=x) fa[tt]=x,son[x].PB(tt);
			}
		}
		dp(pos[n]);write(g[pos[n]]);
    }
};
signed main()
{
    srand(time(0));
    mine::main();
}

Measured memory_bytes: 16636
import java.util.*;

import static java.lang.System.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        Integer[] A = new Integer[M];
        for (int i = 0; i < M; i++) A[i] = sc.nextInt();

        solver(N, M, A);
    }

    public static void solver(int N, int M, Integer[] A) {
        int[] need_matchstick = {-1, 2, 5, 5, 4, 5, 6, 3, 7, 6};

        // Aを数字が大きい順番に並べ替える。同じマッチ数が必要でも数字が大きいものを優先するため
        Arrays.sort(A, Collections.reverseOrder());

        // ちょうどi本のマッチ棒を利用するときの整数の桁数を最大値を動的計画法で計算
        // 桁数を先に求めて、その桁数を満たす整数は後で求める
        int[] digits = new int[N+1];
        Arrays.fill(digits, -1);
        digits[0] = 0;

        for(int n = 1; n <= N; n++){
            for(int a : A){
                int need = need_matchstick[a];
                if(n - need >= 0 && digits[n - need] != -1) {
                    digits[n] = Math.max(digits[n - need] + 1, digits[n]);
                }
            }
        }
        //out.println(Arrays.toString(digits));

        // 桁数を満たす整数を求める
        String numStr = "";
        int rest = digits[N];
        int match = N;
        //out.println(rest);

        while(rest > 0){
            for(int a : A){
                int need = need_matchstick[a];
                //out.println(rest+","+a+","+need);

                if(match >= need && rest - digits[match - need] == 1){
                    numStr += String.valueOf(a);
                    rest --;
                    match -= need;
                    break;
                }
            }

            //try {
            //    Thread.sleep(1000);
            //} catch(InterruptedException e){
            //    e.printStackTrace();
            //}
        }
        out.println(numStr);
    }
}

Measured memory_bytes: 60900
n,m=map(int,input().split())
h=list(map(int,input().split()))
edge=[]
for i in range(n):
    edge.append([])
for i in range(m):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
c=0
for i in range(n):
    f=1
    for j in range(len(edge[i])):
        if h[edge[i][j]]>=h[i]:
            f=0
    c+=f
print(c)

Measured memory_bytes: 29484
#include <bits/stdc++.h>
#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 irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(V, v) for (auto&& V : v)
#define all(x) (x).begin(), (x).end()
using lint = long long;
const int INF = 1 << 29;
const double EPS = 1e-9;
using namespace std;

int main(void) {
  int n;
  cin >> n;
  int left = n / 100;
  int right = n % 100;
  bool ml = false, mr = false;
  if (left <= 12 && left != 0) ml = true;
  if (right <= 12 && right != 0) mr = true;
  if (ml && mr) {
    cout << "AMBIGUOUS";
  } else if (ml) {
    cout << "MMYY";
  } else if (mr) {
    cout << "YYMM";
  } else {
    cout << "NA";
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
import time
time.sleep(1.53)
print(ans)


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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int32 n;
    cin >> n;
    string s;
    cin >> s;
    vector<vector<int32>> cnt(3,vector<int32>(n+1,0));
    vector<int32> t(n+1);
    REP(i,n){
        REP(j,3)cnt[j][i+1] = cnt[j][i];
        if(s[i] == 'R'){
            cnt[0][i+1]++;
            t[i+1] = 2;
        }else if(s[i] == 'G'){
            cnt[1][i+1]++;
            t[i+1] = 3;
        }else{
            cnt[2][i+1]++;
            t[i+1] = 5;
        }
    }
    int64 ans = 0;
    FOR(i,1,n-1){
        FOR(j,i+1,n){
            // int32 pre = ans;
            if(t[i] * t[j] == 6){
                ans += cnt[2][n] - cnt[2][j];
            }else if(t[i] * t[j] == 10){
                ans += cnt[1][n] - cnt[1][j];
            }else if(t[i] * t[j] == 15){
                ans += cnt[0][n] - cnt[0][j];
            }
            if(2 * j - i <= n && t[i] * t[j] * t[2 * j - i] == 30)ans--;
            // cout << i << " " << j << " " << ans - pre << endl;
        }
    }
    ANS(ans);
    return 0;
}

Measured memory_bytes: 3736