akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>
#include<iomanip>
#include<math.h>
#include<bitset>
#include<cassert>
#include<random>
#include<time.h>
using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define MOD 1000000007LL
#define INF 1000000000LL
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

/* --------------------------------------- */
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n;
	cin >> n;
	vector<ll> a(n);
	REP(i,n) cin >> a[i];
	ld avg = 0;
	REP(i,n) avg += a[i];
	avg /= n;
	ld diff = INF;
	ll ans = -1;
	REP(i,n) {
		if(abs(avg - a[i]) < diff - EPS) {
			diff = abs(avg - a[i]);
			ans = i;
		}
	}
	cout << ans << endl;
	return 0;
}
/* --------------------------------------- */


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll zero = 0;
const ll INF = 10000000000000000; //10^16
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;

int main(){
    int H,W,K;
    cin >> H >> W >> K;
    vector<char> cho(H*W);
    for(int i = 0; i < H*W; i++) cin >> cho.at(i);
    vector<int> search(H);
    int tmp;
    int cnt;
    int tmpans;
    int tmpwhi;
    int ans = 100000;
    vector<int> white;
    bool cut = false;
    bool cuttable = true;
    for (int i = 0; i < pow(2, H-1); i++){
        cuttable = true;
        tmp = i;
        cnt = 0;
        for (int h = 0; h < H; h++){
            search.at(h) = cnt;
            if(tmp % 2 == 1) cnt++;
            tmp = tmp / 2;
        }

        cnt = __builtin_popcount(i) + 1;
        tmpans = cnt - 1;
        white.resize(cnt);
        for (int j = 0; j < cnt; j++){
            white.at(j) = 0;
        }
        for (int w = 0; w < W; w++){
            for(int h = 0; h < H; h++){
                if(cho.at(W*h + w) == '1') white.at(search.at(h))++;
            }
            for(int whi : white){
                //printf("%d ", whi);
                if(whi > K){
                    tmpans++;
                    cut = true;
                    break;
                }
            }
            if(cut){
                for(int j = 0; j < cnt; j++){
                    white.at(j) = 0;
                }
                for(int h = 0; h < H; h++){
                    if(cho.at(W*h + w) == '1') white.at(search.at(h))++;
                }
                for(int whi : white){
                    //printf("%d ", whi);
                    if(whi > K){
                        cuttable = false;
                        break;
                    }
                }
                cut = false;
            }
            if(!cuttable) break; 
        }
        if(!cuttable) continue;
        ans = min(ans, tmpans);
        //printf("%d\n", tmpans);

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


}


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

int main(){
	int n;
  	cin >> n;
  	int m = n/100;
  	int ans;
  	if(n <= m*100 + m*10 + m) ans = m*100 + m*10 + m;
  	else ans = (m+1)*100 + (m+1)*10 + m+1;
  	cout << ans << endl;
}

Measured memory_bytes: 256
/* created   : 2019-09-05 10:43:54
 * accepted  : 2019-09-05 15:07:45
 * author    : landcold7
 */
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#ifndef LOCAL
#define trace(...)
#endif
typedef long long ll;

void solve() {
  int n; cin >> n;
  int node = 0;
  vector<vector<int>> g(n * n);
  vector<int> deg(n * n);
  map<pair<int, int>, int> mp;
  for (int i = 1; i <= n; i++) {
    int pr = -1;
    for (int j = 1; j <= n - 1; j++) {
      int v; cin >> v;
      int u = i;
      if (u > v) {
        swap(u, v);
      }
      if (!mp.count({u, v})) {
        mp[{u, v}] = node++;
      }
      if (j == 1) {
        pr = mp[{u, v}];
      }
      else {
        int cr = mp[{u, v}];
        g[pr].push_back(cr);
        deg[cr]++;
        pr = cr;
      }
    }
  }
  trace(deg, g);
  deque<int> dq;
  int cnt = 0;
  for (int i = 0; i < node; i++) {
    if (deg[i] == 0) {
      dq.push_back(i);
      cnt++;
    }
  }
  int ans = 0;
  while (!dq.empty()) {
    ans++;
    int sd = dq.size();
    for (int i = 0; i < sd; i++) {
      int u = dq.front(); dq.pop_front();
      for (auto v : g[u]) {
        if (--deg[v] == 0) {
          dq.push_back(v);
          cnt++;
        }
      }
    }
  }
  cout << (cnt == n * (n - 1) / 2 ? ans : -1) << '\n';
}

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


Measured memory_bytes: 74624
# li = [[0] * 4 for i in range(3)]

# A = list.map(int, input().split())


A, B = map(int, input().split())
ans = 0
for i in range(20000):
    if (i * 0.08) // 1 != A:
        continue

    if (i * 0.1) // 1 != B:
        continue

    print(i)
    ans = 1
    break

if ans == 0:
    print(-1)



Measured memory_bytes: 2940
# 検証のためのACの人のパクリですごめんなさい
N = int(input())
hs = [i for i in map(int, input().split())]

INF = 10*12
dp = [INF]*N

dp[0] = 0
dp[1] = abs(hs[0]-hs[1])
for i in range(2, N):
  dp[i] = min(dp[i-1] +abs(hs[i]-hs[i-1]), dp[i-2] +abs(hs[i]-hs[i-2]))
print(dp[-1])

Measured memory_bytes: 13928
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265359;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };



signed main() {
	int a, p;

	cin >> a >> p;

	int num =  ((a*3 + p )/ 2);

	cout << num << endl;







	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

const (
	initialBufSize = 1e4
	maxBufSize     = 1e6 + 7
)

var buf []byte = make([]byte, maxBufSize)
var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buf, maxBufSize)
}

func main() {
	N := nextInt()
	An := make(map[int]int)
	var sum int
	for i := 0; i < N; i++ {
		A := nextInt()
		An[A]++
		sum += A
	}
	Q := nextInt()
	for i := 0; i < Q; i++ {
		B, C := nextInt(), nextInt()
		nums := An[B]
		sum += (C - B) * nums
		An[C] += An[B]
		An[B] = 0
		fmt.Println(sum)
	}
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func abs(a int) int {
	if a > 0 {
		return a
	} else {
		return -a
	}
}

func pow(p, q int) int {
	res := p
	if q == 0 {
		return 1
	}
	for i := 0; i < q-1; i++ {
		res *= p
	}
	return res
}

func MinOf(vars ...int) int {
	min := vars[0]
	for _, i := range vars {
		if min > i {
			min = i
		}
	}
	return min
}

func MaxOf(vars ...int) int {
	max := vars[0]
	for _, i := range vars {
		if max < i {
			max = i
		}
	}
	return max
}

func gcdof2numbers(a int, b int) int {
	if b == 0 {
		return a
	}
	return gcdof2numbers(b, a%b)
}

func lcmof2numbers(a int, b int) int {
	return a / gcdof2numbers(a, b) * b
}

// マイナスの場合は考慮していない
func fuctorial(a int) int {
	if a == 1 || a == 0 {
		return 1
	} else {
		return fuctorial(a-1) * a
	}
}

func NextPermutation(x sort.Interface) bool {
	n := x.Len() - 1
	if n < 1 {
		return false
	}
	j := n - 1
	for ; !x.Less(j, j+1); j-- {
		if j == 0 {
			return false
		}
	}
	l := n
	for !x.Less(j, l) {
		l--
	}
	x.Swap(j, l)
	for k, l := j+1, n; k < l; {
		x.Swap(k, l)
		k++
		l--
	}
	return true
}

// 素因数分解したmapを返す
func primeFuctorize(n int) map[int]int {
	pf := map[int]int{}
	for i := 2; i*i <= n; i++ {
		for n%i == 0 {
			pf[i]++
			n /= i
		}
	}
	if n != 1 {
		pf[n]++
	}
	return pf
}


Measured memory_bytes: 9708
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}



signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int N;
	int con = 0;
	vector<int> P;
	
	cin>>N;
	
	P.resize(N);
	
	for(int i = 0, minimum = INF; i < N; i++){
		cin>>P[i];
		
		if(P[i] < minimum) con++;
		minimum = min(minimum, P[i]);
	}
	
	cout<<con<<endl;
	
	
	
	
	return 0;
}

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

int main(){
    ll N;  cin >> N;
    vector<ll> div(2e6,0);
    int idx = 0;
    for(ll i=1; i*i<=N; i++){
        if(N%i==0){
            div[idx] = i;
            div[idx+1] = N/i;
            idx += 2;
        }
    }

    ll ans = 0;
    int n = div.size();
    for(ll i=0; i<n; i++){
        if(div[i]==1 || div[i]==0) continue;
        ll m = div[i]-1;
        if(N%m!=0 && N/m==N%m){
            ans += m;
        }
    }
    cout << ans << endl;
}

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

bool check(int x) {
	return 0 <= x and x <= 9;
}

int main(int argc, char const *argv[])
{
	int a, b; cin >> a >> b;
	if (not check(a) or not check(b)) {
		printf("-1\n");
		return 0;
	}
	printf("%d\n", a * b);
	return 0;
}


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

public class Main {


    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
        String word = s.next();
        int cnt = 0;
        for(int i=0;i<word.length();i++){
            if(word.charAt(i)=='+')cnt++;
            else cnt--;
        }
        System.out.println(cnt);


    }




}


class Scanner
{
    StringTokenizer st;
    BufferedReader br;

    public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

    public String next() throws IOException
    {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

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

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

    public String nextLine() throws IOException {return br.readLine();}

    public double nextDouble() throws IOException
    {
        String x = next();
        StringBuilder sb = new StringBuilder("0");
        double res = 0, f = 1;
        boolean dec = false, neg = false;
        int start = 0;
        if(x.charAt(0) == '-')
        {
            neg = true;
            start++;
        }
        for(int i = start; i < x.length(); i++)
            if(x.charAt(i) == '.')
            {
                res = Long.parseLong(sb.toString());
                sb = new StringBuilder("0");
                dec = true;
            }
            else
            {
                sb.append(x.charAt(i));
                if(dec)
                    f *= 10;
            }
        res += Long.parseLong(sb.toString()) / f;
        return res * (neg?-1:1);
    }

    public boolean ready() throws IOException {return br.ready();}


}

Measured memory_bytes: 25280
//------------------------------>> tsukasa_diary's template <<------------------------------//
#include <bits/stdc++.h>
using namespace std;

using lint = long long;
using pii = pair< int, int >;

template< typename T > using Vec = vector< T >;

template< typename T > bool inRange(T x, T lb, T ub) { return lb <= x && x < ub; }
template< typename T > bool inRange(T x, T y, T lb, T ub) { return in_range(x, lb, ub) && in_range(y, lb, ub); }

template< typename T > void modAdd(T& a, T b, T mod) { a = (a + b + mod) % mod; }
template< typename T > void modMul(T& a, T b, T mod) { a = (a * b) % mod; }
template< typename T > void minUpdate(T& a, T b) { a = min(a, b); }
template< typename T > void maxUpdate(T& a, T b) { a = max(a, b); }

int bitCount(int x) { return __builtin_popcount(x); }
int bitCount(lint x) { return __builtin_popcountll(x); }

const int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
const int Dx[8] = {0,1,1,1,0,-1,-1,-1}, Dy[8] = {-1,-1,0,1,1,1,0,-1};
const double EPS = 1e-9;
const double PI = acos(-1);

//--------------8---------------->> coding space <<-----------------8-------------//



int main() {
	int Q;
	cin >> Q;
	
	map< int, int > cnt;
	set< pii > abs_set;
	
	lint sum_abs = 0, sum_b = 0;
	pii center = pii(0, 0);
	
	for (int i=0; i<Q; ++i) {
		int x;
		cin >> x;
		
		if (x == 1) {
			lint a, b;
			cin >> a >> b;
			
			int n = abs_set.size();
			pii add = pii(a, cnt[a]);
			abs_set.insert(add);
			cnt[a]++;
			sum_b += b;
			
			//cerr << "Add : " << add.first << " " << add.second << endl;
			
			if (i == 0) {
				center = add;
			}
			else {
				sum_abs += abs(center.first - a);
				if (n & 1) { // odd
					if (center > add) {
						auto it = abs_set.lower_bound(center);
						--it;
						center = *it;
					}
				}
				else { // even
					if (center < add) {
						auto it = abs_set.upper_bound(center);
						sum_abs -= (it->first - center.first);
						center = *it;
					}
				}
			}
			//cerr << "Center : " << center.first << " " << center.second << endl;
		}
		else {
			cout << center.first << " " << sum_abs + sum_b << endl;
		}
	}
}
//--------------8---------------->> coding space <<-----------------8-------------//

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

int main(){
	string s;
	cin >> s;
	
	int ans = 0;
	int n = s.length();
	rep(i, n/2){
		if(s[i] != s[s.size()-1-i]) ans++;
	}
	
	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;

struct SegmentTree {
    struct Node {
        Node operator+(const Node& o) const {
            return { v + o.v };
        }
        int v;
    };
    SegmentTree(int n, Node o) : o0(o), n(n) {
        for (m = 2; m < n; m *= 2);
        st = vector<Node>(m * 2, o0);
    }
    void construct() {
        for (int k = m; k > 1; k /= 2) {
            for (int i = k / 2; i < k; i++) {
                st[i] = st[i * 2] + st[i * 2 + 1];
            }
        }
    }
    void update(int i, const Node& o) {
        for (st[i += m] = o; i /= 2, i > 0;) st[i] = st[i * 2] + st[i * 2 + 1];
    }
    Node query(int i0, int i1, int i, int k, int w) {
        if (i1 - i0 == w) return st[i];
        int l = k + w / 2;
        Node o;
        if (i0 < l) o =     query(i0, min(i1, l), i * 2 + 0, k, w / 2); else o = o0;
        if (l < i1) o = o + query(max(l, i0), i1, i * 2 + 1, l, w / 2);
        return o;
    }
    vector<Node> st;
    Node o0;
    int n, m;
};

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

    int n, k;
    cin >> n >> k;

    vector<int64_t> b(n + 1);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        b[i + 1] = b[i] + (a - k);
    }

    vector<int> c(n + 1);
    for (int i = 0; i <= n; i++) {
        c[i] = i;
    }
    sort(c.begin(), c.end(), [&](int i0, int i1) {
        return b[i0] < b[i1];
    });

    vector<int> d(n + 1);
    int m = 0;
    for (int i = 0; i <= n; i++) {
        if (i > 0 && b[c[i]] != b[c[i - 1]]) m++;
        d[c[i]] = m;
    }

    SegmentTree st(m + 1, { 0 });
    int64_t r = 0;
    for (int i = 0; i <= n; i++) {
        if (i > 0) r += st.query(0, d[i] + 1, 1, 0, st.m).v;
        st.update(d[i], { st.st[st.m + d[i]].v + 1 });
    }
    //for (int i = 0; i <= n; i++) {
    //    for (int j = 0; j < i; j++) {
    //        if (d[j] <= d[i]) r++;
    //    }
    //}

    cout << r << endl;

    return 0;
}

Measured memory_bytes: 5504
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<string.h>
using namespace std;
#define N 1000
#define M 100000
#define S second
#define F first
#define MP(i, j) make_pair((i), (j))
#define INF 1e9
typedef pair<int, int> P;

vector<int> vec[N + 1][2], vec2, vec3;
P yoko[M];
int s[N + 1];
int main() {
	int n, m, h, k;
	while (cin >> n >> m >> h >> k && n && m && h && k) {
		int ans = INF, sum = 0;
		memset(s, 0, sizeof s);
		memset(yoko, 0, sizeof yoko);
		vec2.clear(); vec3.clear();
		for (int i = 0; i < n; i++) {
			scanf("%d", s + i);
			vec[i][0].clear();
			vec[i][1].clear();
		}
		for (int i = 0; i < m; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			yoko[i] = MP(b, a);
		}
		sort(yoko, yoko + m);
		for (int i = 0; i < n; i++) {
			vec[i][0].push_back(i);
		}
		for (int i = 0; i < m; i++) {
			//		cout << 1 << endl;
			int a = yoko[i].S;
			a--;
			int sz = vec[a][1].size();
			for (int j = 0; j < vec[a + 1][1].size(); j++) {
				vec[a][1].push_back(vec[a + 1][1][j]);
			}
			//		cout << 2 << endl;
			vec[a + 1][1].clear();

			for (int j = 0; j < sz; j++) {
				vec[a + 1][1].push_back(vec[a][1][j]);
			}
			if (sz)
				vec[a][1].erase(vec[a][1].begin(), vec[a][1].begin() + sz);
			//		cout << 3 << endl;
			for (int j = 0; j < vec[a + 1][0].size(); j++) {
				vec[a][0].push_back(vec[a + 1][0][j]);
				vec[a + 1][1].push_back(vec[a + 1][0][j]);
			}
			//		cout << 4 << endl;
			vec[a + 1][0].erase(vec[a + 1][0].begin(), vec[a + 1][0].end());
			for (int j = 0; j < 1; j++) {
				vec[a + 1][0].push_back(vec[a][0][j]);
				vec[a][1].push_back(vec[a][0][j]);
			}
			if (vec[a][0].size())
				vec[a][0].erase(vec[a][0].begin(), vec[a][0].begin() + 1);
			//		cout << 5 << endl;
		}
		for (int i = 0; i < n; i++) {
			if (k >= vec[i][0][0] + 1) {
				sum += s[i];
				vec2.push_back(i);
			}
			else {
				vec3.push_back(i);
			}
			sort(vec[i][1].begin(), vec[i][1].end());
		}
		for (int i = 0; i < vec2.size(); i++) {
			for (int j = 0; j < vec3.size(); j++) {
				if (s[vec2[i]] > s[vec3[j]]) {
					if (binary_search(vec[vec3[j]][1].begin(), vec[vec3[j]][1].end(), vec[vec2[i]][0][0])) {
						ans = min(ans, sum - s[vec2[i]] + s[vec3[j]]);
					}
				}
			}
		}
		ans = min(ans, sum);
		cout << ans << endl;
	}
}

Measured memory_bytes: 4408
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (__typeof(a) i=(a); i<(b); ++i)
#define iter(it,c) for (__typeof((c).begin()) \
  it = (c).begin(); it != (c).end(); ++it)
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
const int INF = ~(1<<31);

const double EPS = 1e-9;
const double pi = acos(-1);
typedef unsigned long long ull;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
template <class T> T smod(T a, T b) {
  return (a % b + b) % b; }

vector<ii> factor(ll n)
{
    vector<ii> res;
    ll i = 2;
    while(i*i <= n)
    {
        ll cnt = 0;
        while(n%i == 0) cnt++, n/=i;
        if(cnt) res.push_back(ii(i,cnt));
        i++;
    }

    if(n > 1) res.push_back(ii(n, 1));

    return res;
}

ll n;
ll fav(vector<ii>& v, int at, ll k)
{
    if(at == v.size())
    {
        if((n-k)%k == 0)
        {
            ll m = (n-k)/k;
            if(m > 0 && n/m == n%m) return m;
        }
        return 0;
    }
    ll x = 1, res = 0;
    rep(i,0,v[at].second+1)
    {
        res += fav(v, at+1, k*x);
        x *= v[at].first;
    }
    return res;
}

int main()
{
    cin >> n;

    vector<ii> f = factor(n);
    cout << fav(f, 0, 1) << endl;
}


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

int main() {
	int k, a, b;

	cin >> k;
	cin >> a >> b;

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

Measured memory_bytes: 3624
def main():
    N, A, B = map(int, input().split())

    ret = 0
    rep, rest = divmod(N, A + B)
    ret += rep * A
    ret += min(A, rest)

    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

template<class T>
bool ChangeMax(T&a,const T&b){
  if(a >= b) return false;
  a = b;    return true;
}

template<class T>
bool ChangeMin(T&a,const T&b){
  if(a <= b) return false;
  a = b;    return true;  
}

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  int h,w; cin >> h >> w;
  char c[100][100];
  for(int i = 0; i < h; ++i){
    for(int j = 0; j < w; ++j){
      cin >> c[i][j];
    }
  }
  int mx[] = {-1,0,0,1};
  int my[] = {0,-1,1,0};
  for(int i = 1; i < h-1; ++i){
    for(int j = 1; j < w-1; ++j){
      if(c[i][j] == '.')continue;
      bool f = false;
      for(int k = 0; k < 4; ++k){
	if(c[i+my[k]][j+mx[k]] == '#')f = true;
      }
      if(!f){
	cout << "No" << endl;
	return 0;
      }
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
from sys import stdin
N=int(stdin.readline().rstrip())
data=[int(x) for x in stdin.readline().rstrip().split()]
from statistics import mean
data_mean=mean(data)
def calc_(n):
    return abs(n-data_mean)
 
data2 = list(map(calc_, data))
data3=list(data2)
result=data3.index(min(data3))
print(result)

Measured memory_bytes: 5332
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define PI acos(-1)
#define EPS 1e-5
#define sz(v) ((int)(v).size())
#define all(v) v.begin(),v.end()
#define forn(i, n) for(ll i=0;i<(ll)n;i++)
#define fi first
#define se second
 

int main() {
	int a, b;
	cin >> a >> b;
	cout << a*b << endl;

	return 0;
}



Measured memory_bytes: 3560
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,x,n) for(int i=(x);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define int long long
using namespace std;
const int MOD=1e9+7;
const int INF=1e10;

int memo[1000006];

int fac(int n){
  if(n==0)return 1;
  else if(memo[n]>0)return memo[n];
  else return memo[n]=n*fac(n-1)%MOD;
}

int mod_pow(int b,int p){
  if(p==0)return 1;
  else if(p%2==0)
    return mod_pow(b*b%MOD,p/2);
  else
    return b*mod_pow(b*b%MOD,(p-1)/2)%MOD;
}

signed main(){
  int h,w,a,b;
  cin>>h>>w>>a>>b;

  int ans=0;

  rep(i,h-a){

    int A=fac(b-1+i);
    int B=fac(b-1);
    int C=fac(i);

    int D=fac(h+w-2-i-b);
    int E=fac(w-1-b);
    int F=fac(h-1-i);

    int tmp1=A%MOD*mod_pow(B*C%MOD,MOD-2)%MOD;
    int tmp2=D%MOD*mod_pow(E*F%MOD,MOD-2)%MOD;

    ans+=tmp1*tmp2%MOD;

    //cout<<A<<' '<<B<<' '<<C<<' '<<D<<' '<<E<<' '<<F<<endl;

  }

  cout<<ans%MOD<<endl;



  return 0;
}


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

using namespace std;

int main ()
{
	string s;
	cin >> s;
	int ans = 0;
	for (int i=0, j=s.length()-1; i<j; i++, j--){
		if (s[i] != s[j]) ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
n = int(input())
weights = list(map(int, input().split()))
ans = all_weights = sum(weights)
add_list = [0]*n
for index,weight in enumerate(weights):
    add_list[index] = weight + (add_list[index-1] if index !=0 else 0)
    ans = min(abs(all_weights - 2* add_list[index]) ,ans)
print(ans)

Measured memory_bytes: 38384
use std::io::*;
use std::str::FromStr;
 
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}
 
fn main() {
    let n: usize = read();
    let y: i32 = read();
    for i in 0..n+1 {
        for j in 0..n+1-i {
            let k = n - i - j;
            if (10000 * i + 5000 * j + 1000 * k) as i32 == y {
                println!("{} {} {}", i, j, k);
                return;
            }
        }
    }
    println!("-1 -1 -1");
}

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

using namespace std;
typedef long long ll;
#define int ll

template<typename T1,typename T2> inline void chmin(T1 &a, T2 b){ if(a > b) a = b; }
template<typename T1,typename T2> inline void chmax(T1 &a, T2 b){ if(a < b) a = b; }

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
const int MAX_N = 100010;

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

    string S;
    cin >> S;
    if(S == "ABC") {
        printf("ARC\n");
    }
    else {
        printf("ABC\n");
    }

    return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <stdio.h>
using namespace std;

int main() {

    int a    = 0;
    int b    = 0;
    int d    = 0;
    int r    = 0;
    double f = 0.0;

    cin >> a;
    cin >> b;

    d = a / b;
    r = a % b;
    f = (double)a / (double)b;
 
//    cout << d << " " << r << " " << f << std::endl;
    printf("%d %d %f\n",d,r,f);
}

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

vector<long long> pri_fac(long long N, string mode){
    if(mode == "unique"){
        vector<long long> yakusu;
        long long now = 0; 
        long long a = 2;
        while(N >= a*a){
            if(N%a == 0){
                if (a != now){
                    yakusu.push_back(a);
                    now = a;
                }
                N /= a;
            }else{
                a++;
            }
        } 
        if(N != now & N != 1) yakusu.push_back(N);
        return yakusu;
    }else if(mode == "all"){
        vector<long long> yakusu;
        long long now = 0; 
        long long a = 2;
            while(N >= a*a){
                if(N%a == 0){
                    yakusu.push_back(a);
                    N /= a;
                }else{
                    a++;
                }
            } 
        if(N != 1) yakusu.push_back(N);
        return yakusu;
    }
}

int main(){
    long long N;
    cin >> N;

    /*
    vector<long long> test;

    test = pri_fac(N,"unique");

    for(int i=0;i<test.size();i++){
        cout << test[i] << endl;
    }
    */

    

    while(true){
        vector<long long> temp;
        temp = pri_fac(N,"all");
        if(temp.size() == 1){
            break;
        }
        if(N%2 == 0) N++;
        else N += 2;
    }

    cout << N << endl;
    return 0;
}

Measured memory_bytes: 256
def mi():return map(int,input().split())

l=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

k=int(input())

print(l[k-1])



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

#define rep(i, N) for (int i = 0; i < N; i++)
#define rep1(i, N) for (ll i = 1; i <= N; i++)
#define repr(i, N) for (ll i = N-1; i >= 0; i--)
#define repr1(i, N) for (ll i = N; i > 0; i--)

using ll = long long;
using namespace std;

int main(){
    int N,cnt,ans=0;
    cin >> N;

    for(int i = 1;i <= N; i+=2){
        cnt=0;
        rep1(j, i){
            if(i%j==0) cnt++;
            if(cnt>8) break;
        }
        if(cnt == 8) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <time.h>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <array>
#include <string>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mp make_pair
#define eb emplace_back
#define f first
#define s second
#define sz(x) (ll)x.size()
using namespace std;
using namespace __gnu_pbds;

typedef long long int ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> osSet;

using pll = pair<ll, ll>;

const ll maxN = 1e7;
const ll INF = 1e17;
const ll MOD = 1e9 + 7;

ll xs[] = {-1, 1, 0, 0, -1, 1, 1, -1};
ll ys[] = {0, 0, -1, 1, -1, 1, -1, 1};

ll segtree[maxN << 2];
ll lazy[maxN << 2];
ll A[maxN];

inline ll left(ll x){
	return x << 1;
}

inline ll right(ll x){
	return (x<<1) + 1;
}

ll func(ll x){
	return (x*(x+1))/2;
}

ll _pow(ll b, ll p){
	if(p == 0) return 1;
	if(p == 1) return b;
	ll exB = b*b;
	if(p&1) return b*_pow(exB, p/2);
	return _pow(exB, p/2);
}

int main(){
	cin.sync_with_stdio(false);
	cin.tie(0);
	ll a, b, c;
	cin >> a >> b >> c;
	ll k;
	cin >> k;
	bool ns = false;
	while(b<=a){
		b*=2;
		k--;
		if(k == 0)
			break;
	}
	if((1<<k)*c > b or c>b)
		cout << "Yes";
	else
		cout << "No";
	return 0;
}

Measured memory_bytes: 3640
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
count = 0
S.append(0)

def linearSearch(t):
  i = 0
  S[n] = t
  while S[i] != t:
    i += 1
  if i == n:
    return 0
  return 1

for t in T:
  count += linearSearch(t)
print(count)


Measured memory_bytes: 6552
"""
Writer: SPD_9X2
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2439

1位から順番に見ていく。
-ならそこの順位に決めざるを得ない

Uなら、左に空いた空きマスから1つ選んでそこに入れる(空きマスは減る)
Dなら、…？

dpであることは分かっている
重要なのはどの状態をまとめるか…

-は関係ないので無視してUDだけの問題にする
UDの列に通し番号を付ける。Uはそれより右に、Dは左にもっていかなくてはならない
そのような並び替えが構成できなくなるのは、左にもとよりUが多い場合・・・

Uだけの入れ方を考えてみる(Dはどこに入っても構わない)
左から見ていくと、入れる・入れないを決め、今までに出たUの中から1つ選んで入れればよい
→ただのdpで解ける

Dだけの入れ方も同様に分かる

あらかじめU,Dにおいてdpをしておく？

udp[左からi番目にUが入る場合のUの入り方][j][k] =
ん～？？？？？

=====解説を見た=====

Uならば、それより右に入れなきゃいけない→保留枠に入れ、Uのあったマスを開けておく
Dならば、そこにあったDを左の空きますにぶち込み、保留の中から1つUを選んでぶち込む or　空きますにする
→空きマスは1つ減る or 減らない

空きマスの数 = 保留の数なので、 O(N**2)で解ける

"""

n = int(input())

dp = [0] * (n+1)
dp[0] = 1
mod = 10**9+7

for loop in range(n):

    c = input()
    ndp = [0] * (n+1)
    if c == "-":
        continue

    
    elif c == "U":
        for i in range(n+1):

            if i != n: #保留に入れて空きますにする
                ndp[i+1] = dp[i]
                ndp[i+1] %= mod

            #保留に入れ、保留から1つ取り出して入れる

            ndp[i] += dp[i] * i
            ndp[i] %= mod
            

    else:
        for i in range(0,n+1):

            if i != 0: #そこにあったのは左の空きますに移動 & そのマスに保留からぶち込む
                ndp[i-1] += dp[i] * i * i
                ndp[i-1] %= mod

            #そこにあったのは左の空きますに、そこは空きますにする

            ndp[i] += dp[i] * i
            ndp[i] %= mod
    

    dp = ndp
    #print (dp)

print (dp[0])



Measured memory_bytes: 5616
#include<iostream>
#include <complex>
#include <vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<list>
#include <iterator>
#include <utility>
#include <numeric>
using namespace std;

#define intt long long




int main() {
	int N;

	vector<int> A;
	intt x, y;
	cin >> N;
	intt sum = 0;
	A.resize(N);
	int size = 0;
	int	flag=0;

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

	sort(A.begin(), A.end());
	int max = N;

	int a, b, c, d;
	for (int i = 0; i != N;i++) {
		if (size < 1) {
			x = A[N -1];
			y = A[N - 1];
			A.erase(A.begin() + A.size() - 1);
			size += 1;
			continue;
		}


		a = abs(x - A[0]);
		b = abs(y - A[0]);
		c = abs(x - A[A.size() - 1]);
		d = abs(y - A[A.size() - 1]);

		if (a >= b && a >= c && a >= d) {
			sum += abs(A[0] - x);
			x = A[0];
			A.erase(A.begin());
		}
		else if (b >= a && b >= c && b >= d) {
			sum += abs(A[0] - y);
			y = A[0];
			A.erase(A.begin());
		}
		else if (c >= a&& c >= b&& c >= d) {
			sum += abs(A[A.size() - 1] - x);

			x = A[A.size() - 1];
			A.erase(A.begin() + A.size() - 1);
		}
		else if (d >= a&& d >= b&&d >= c) {
			sum += abs(A[A.size() - 1] - y);

			y = A[A.size() - 1];
			A.erase(A.begin() + A.size() - 1);
		}


	}
	cout << sum << endl;

	return 0;

}

Measured memory_bytes: 768
/**
*    created: 14.06.2020 21:02:31
**/
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using namespace std;

signed main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int x, y;
    cin >> x >> y;
    rep(i,100) rep(j,100) {
        if (2 * i + 4 * j == y && i + j == x) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3636
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100005,MOD=1000000007;
const long long LLF=0x3F3F3F3F3F3F3F3FLL;

int N;
long long A,B,S[MAXN];
int f[MAXN],sum[MAXN];

int main()
{
	scanf("%d%lld%lld",&N,&A,&B);
	for(int i=1;i<=N;i++)
		scanf("%lld",&S[i]);
	if(A>B)
		swap(A,B);
	for(int i=3;i<=N;i++)
		if(S[i]-S[i-2]<A)
		{
			puts("0");
			return 0;
		}
	S[N+1]=LLF;
	
	f[0]=sum[0]=1;
	int l=0,r=0;
	for(int i=1;i<=N+1;i++)
	{
		while(r<i-1&&S[i]-S[r+1]>=B)
			r++;
		if(l<=r)
			(f[i]+=(sum[r]-(l==0?0:sum[l-1])+MOD)%MOD)%=MOD;
		sum[i]=(sum[i-1]+f[i])%MOD;
		if(i!=1&&S[i]-S[i-1]<A)
			l=i-1;
	}
	printf("%d\n",f[N+1]);
	
	return 0;
}


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

public class Program
{
	public static void Main()
	{
		var inputNum = _GetIntReadLine().ToString();
		Console.WriteLine(inputNum.Contains("7") ? "Yes" : "No");
	}

	private static string		_GetReadLine()		  { return Console.ReadLine(); }
	private static int			_GetIntReadLine()	  { return int.Parse(_GetReadLine()); }
	private static List<string> _GetListReadLine()	  { return _GetReadLine().Split(' ').ToList(); }
	private static List<int>	_GetIntListReadLine() { return _GetListReadLine().Select(iText => int.Parse(iText)).ToList(); }
}

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

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int K; cin >> K;
	ll ans = 0;
	for (int i = 1; i <= K; i++)
		for (int j = 1; j <= K; j++)
			for (int k = 1; k <= K; k++)
				ans += gcd(i, gcd(j, k));
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3664
n=int(input())
from math import gcd
a,b=map(int,input().split())
temp=a+b
for i in range(1,n):
    c,d=map(int,input().split())
    j=c+d
    
    x=max(a-c,0)//c
    if max(a-c,0)%c!=0:
        x+=1
    y=max(b-d,0)//d
    if max(b-d,0)%d!=0:
        y+=1
    z=max(temp-j,0)//j
    if max(temp-j,0)%j!=0:
        z+=1
    l=[x,y,z]
    temp=max(l)*j+j
    a=max(l)*c+c
    b=max(l)*d+d
        
print(temp)

Measured memory_bytes: 73732
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <bitset>
#include <array>
#include <deque>
#include <queue>
#define all(x) (x).begin(),(x).end()

void solve(){

}
int main(){
    int x,a,b;
    cin >> x >> a >> b;
    if (abs(x-a) < abs(x-b)){
        cout << 'A' << endl;
    } else {
        cout << 'B' << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<unordered_set>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod;
typedef pair<ll,ll> P;
vector<P> v;
int main(){
  ll n;cin>>n;
  for(int i=0;i<n;i++){
    ll a,b;cin>>a>>b;
    v.push_back(make_pair(b,a));
  }
  sort(v.begin(),v.end(),greater<P>());
  ll cnt=1e17;
  for(int i=0;i<n;i++){
    cnt=min(cnt,v[i].first);
    cnt-=v[i].second;
  }
  cout<<(cnt>=0?"Yes":"No")<<endl;
  return 0;
}


Measured memory_bytes: 6256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using ll = long long;
using P = pair<ll, ll>;
const int mod = 1000000007;
const ll INF = 1001001001001;


int main(){
    ll n, x, d;
    cin >> n >> x >> d;
    
    if (d==0) {
        if (x==0) {
            cout << "1" << endl;
        }
        else {
            cout << n+1 << endl;
        }
        return 0;
    }
    
    if (d<0) {
        x = -x;
        d = -d;
    }

    map<ll, vector<P>> mp;
    for (ll i=0; i<=n; i++) {
        ll s = x * i;
        ll l = d*(i*(i-1)/2);
        ll r = d*((n*(n-1))/2-(n-i)*(n-i-1)/2);
        mp[s%d].emplace_back(s+l, s+r+d);
    }

    ll ans = 0;
    for (auto m: mp) {
        vector<P> ev;
        for (auto e: m.second) {
            ev.emplace_back(e.first, 1);
            ev.emplace_back(e.second, -1);
        }
        sort(ev.begin(), ev.end());
        ll cnt = 0;
        ll pre = -INF;
        for (auto p: ev) {
            if (cnt) ans += (p.first-pre)/d;
            cnt += p.second;
            pre = p.first;
        }
    }
    cout << ans << endl;
    
    /*
    vector<pair<ll, ll>> data(n+1);
    rep(i, n+1) {
        data[i].first = (i*x)%d;
        data[i].second = i*x;
    }
    sort(data.begin(), data.end());
    
    ll max = -INF;
    ll min = INF;
    
    rep(i, n+1) {
        ll v1 = (i*(i-1))/2;
        ll v2 = ((n-1)*n)/2 - ((n-i)*(n-i-1))/2;
        ll w1 = i*x + v1*d;
        ll w2 = i*x + v2*d;
        cout << w1 << " " << w2 << endl;
        if (i==0 || data[i].first!=data[i-1].first) {
            ans += v2 - v1 + 1;
            max = -INF;
            min = INF;
        }
        else {
            if (w1>max || w2<min) {
                ans += v2 - v1 + 1;
            }
            else {
                if (w2>max) {
                    ans += (w2-max)/d;
                }
            }
        }
        if (w1<min) w1 = min;
        if (w2>max) w2 = max;
    }
    
    cout << ans << endl;
    */
    return 0;
}


Measured memory_bytes: 22144
#include <bits/stdc++.h>
//#define int long long

using namespace std;
using LL = long long;
using P = pair<int, int>;

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e15;
const int MOD = 1e9 + 7;

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

template <typename T>
struct Edge {
    int from, to;
    T cost;
    Edge(int to, T cost) : from(-1), to(to), cost(cost) {}
    Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
};

template <typename T>
using Edges = vector<Edge<T>>;
template <typename T>
using AdjList = vector<Edges<T>>;

template <typename T>
class Dijkstra {
    private:
        T INF = numeric_limits<T>::max() / 10;
        int V;           // 頂点数
        AdjList<T> adj;  // adj[始点][動的配列で始点から伸びる枝]
        vector<int> prever;

    public:
        Dijkstra(int n);
        vector<T> cost;
        void AddEdge(int f, int t, int c);
        bool HasPath(int t);                 // tに至るパスはあるか
        vector<int> GetShortestPath(int t);  // tへの最短路
        void Run(int f);
};

template <typename T>
Dijkstra<T>::Dijkstra(int n) : 
    V(n + 1), adj(V), prever(vector<int>(V, -1)), cost(V)
{
    fill(cost.begin(), cost.end(), INF);
}

template <typename T>
void Dijkstra<T>::AddEdge(int f, int t, int c) {
    adj[f].push_back(Edge<T>(t, c));
}

template <typename T>
bool Dijkstra<T>::HasPath(int t) {
    return cost[t] != INF;
}

template <typename T>
vector<int> Dijkstra<T>::GetShortestPath(int t) {
    vector<int> path;
    for (; t != -1; t = prever[t]) path.push_back(t);

    reverse(path.begin(), path.end());
    return path;
}

template <typename T>
void Dijkstra<T>::Run(int firstNode) {
    using Pi = pair<T, int>;
    priority_queue<Pi, vector<Pi>, greater<Pi>> pq;

    cost[firstNode] = 0;
    pq.push(Pi(cost[firstNode], firstNode));

    while (!pq.empty()) {
        Pi currentEdge = pq.top();
        pq.pop();
        if (cost[currentEdge.second] < currentEdge.first) continue;

        for (Edge<T> tmp : adj[currentEdge.second]) {
            T sumCost = currentEdge.first + tmp.cost;
            if (cost[tmp.to] > sumCost) {
                cost[tmp.to] = sumCost;
                prever[tmp.to] = currentEdge.second;
                pq.push(Pi(cost[tmp.to], tmp.to));
            }
        }
    }
}

/*************** using variables **************/
int n, q, k;
/**********************************************/

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

    cin >> n;
    Dijkstra<LL> dij(n);
    REP(i, n-1){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        dij.AddEdge(a, b, c);
        dij.AddEdge(b, a, c);
    }
    cin >> q >> k;
    k--;
    dij.Run(k);
    REP(i, q){
        int x, y;
        cin >> x >> y;
        x--; y--;
        cout << dij.cost[x] + dij.cost[y] << endl;
    }
}


Measured memory_bytes: 11504
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define i64 long long int
#define ran 101111
int n,col[ran];
i64 z[ran];
vector<pair<int, int> > e[ran];

int dfs(int i, int cc, i64 zz) {
	if (col[i] != 0) {
		if (col[i] == cc) {
			if (z[i] == zz)return 1;
			return -1;
		}
		else {
			i64 cur = (cc == -1 ? zz - z[i] : z[i] - zz);
			if (cur % 2)
				return -1;
			z[1] = cur / 2;
			return 0;
		}
	}
	col[i] = cc;
	z[i] = zz;
	for (auto it : e[i]) {
		int ret = dfs(it.first, -cc, it.second - zz);
		if (ret != 1)return ret;
	}
	return 1;
}

bool f[ran];i64 val[ran];
int dfs2(int i,i64 vv) {
	if (vv <= 0)return false;
	if (f[i]) {
		return vv == val[i];
	}
	f[i] = true;
	val[i] = vv;
	for (auto it : e[i]) {
		if (!dfs2(it.first, it.second - vv))
			return 0;
	}
	return 1;
}

int main() {
	int m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++){
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		e[x].push_back(make_pair(y, z));
		e[y].push_back(make_pair(x, z));
	}
	int tmp = dfs(1, 1, 0);
	if (tmp == -1) {
		puts("0");
		return 0;
	}
	if (tmp == 0) {
		i64 cur = z[1];
		printf("%d\n", dfs2(1, cur));
		return 0;
	}
	i64 L = 1, R = 10000000000LL;
	for (int i = 1; i <= n; i++)
		if (col[i] == 1) {
			L = max(L, -z[i] + 1);
		}
		else {
			R = min(R, z[i] - 1);
		}
	i64 c = R - L + 1;if (c < 0)c = 0;
	printf("%d\n", (int)c);
	return 0;
}

Measured memory_bytes: 11648
import java.util.*;
import java.util.stream.*;

public class Main {
  public static void main(String[] args) {
    Main main = new Main();
    System.out.println(main.solve());
  }

  String s;

  public Main() {
    Scanner sc = new Scanner(System.in);
    try {
      s = sc.next();
    } finally {
      sc.close();
    }
  }

  String solve() {
    return s.substring(0, 3);
  }
}


Measured memory_bytes: 35888
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)
#define P pair<int,int>
const int MOD=1e9+7;
const int INF=2e9;


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

    int a,b,c;
    cin >> a >> b >> c;
    if (b-a==c-b) cout << "YES" << endl;
    else cout << "NO" << endl;
    

    return 0;   
}


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

using namespace std;

#define REP(i,n)	for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPS(i,s,n)	for(int i=(s), i##_len=(n); i<i##_len; ++i)

#define ALL(obj)	(obj).begin(),(obj).end()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define VEC vector

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int 			ll;

typedef pair<int,int>			P;
typedef vector<int>				Vint;
typedef vector<Vint>			VV;

template<typename T>string join(const v(T)&v)
{stringstream s;REP(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define MAX 		100010


const ll LINF = (ll)9e18+7;		//
const int INF = 100100100;			//2,147,483,647 (Max int)
const ll MOD = 1e9+7;
// テンプレ終了
//====================================================================//

// int DP[MAX];

// 
bool isOK(ll target, ll key) {
    if (target > key) return true;
    else return false;
}

// 汎用的な二分探索のテンプレ
ll binary_search(vector<ll> &a,ll key) {
    ll left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    ll right = (ll)a.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    /* どんな二分探索でもここの書き方を変えずにできる！ */
    while (right - left > 1) {
        ll mid = left + (right - left) / 2;

        if (isOK(a[mid], key)) right = mid;
        else left = mid;
    }

    /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
    return left;
}

int main(){
	int N,M;
	ll K; cin >> N >> M >> K;
	vector<ll> A(N+1,0),B(M+1,0);
	REPS(i,1,N+1){cin >> A[i];A[i]+=A[i-1];}
	REPS(i,1,M+1){cin >> B[i];B[i]+=B[i-1];}
	B.push_back(LINF);

	ll ans = 0;

	REP(i,N+1){
		if(A[i] > K)break;
		ll t = max(binary_search(B,(ll)K-A[i]),0LL);
		// cout << K-A[i] << endl;
		ans = max((ll)t+i,ans);
		// cout << t << endl;
	}

	cout << ans << endl;

	return 0;
}
 



Measured memory_bytes: 8008
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <ios>
#include <iomanip>
int main() {
    int N,M;
    std::cin >> N >> M;
    std::vector<std::vector<int>> City(N+1,std::vector<int>(0,0));
    std::vector<std::pair<int,int>> Input(M+1);
    for(int i=1;i<M+1;i++){
        int P_in,C_in;
        std::cin >> P_in >> C_in;
        City[P_in].push_back(C_in);
        Input[i].first = P_in;
        Input[i].second = C_in;
    }
    // 各県ごとに市を整列
    for(int i=1;i<N+1;i++){
        std::sort(City[i].begin(),City[i].end());
    }

    for(int i=1;i<M+1;i++){
        std::cout << std::setfill('0') << std::right << std::setw(6) << Input[i].first;
        int CityNum;
        CityNum = std::lower_bound(City[Input[i].first].begin(),City[Input[i].first].end(),Input[i].second) - City[Input[i].first].begin() + 1;
        std::cout << std::setfill('0') << std::right << std::setw(6) << CityNum << std::endl;
    }
    return 0;
}

Measured memory_bytes: 9488