akhauriyash/Code-Regression huggingface dataset:
/*
Problem : AtCoder Beginner Contest 114 - D
Algorithm : math
Status :
*/
#include <bits/stdc++.h>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;

int n,len,ans;
int prime[105],cnt[105];

bool isPrime(int k){
	for(int i = 2;i * i <= k;i++){
		if(k % i == 0)
		    return false;
	}
	return true;
}

void cntPrimeDivisors(int k){
	int i = 1;
	while(1){
		if(prime[i] > k || prime[i] == 0)
		    break;
		while(k % prime[i] != 0)
		    i++;
		while(k % prime[i] == 0){
			cnt[i]++;
			k /= prime[i];
		}
	}
}

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d",&n);
	for(int i = 2;i <= n;i++){
		if(isPrime(i))
		    prime[++len] = i;
	}
	for(int i = 2;i <= n;i++)
 	    cntPrimeDivisors(i);
	for(int i = 1;i <= len;i++){
		if(cnt[i] >= 74)
		    ans++;
	}
	for(int i = 1;i <= len;i++){
		for(int j = i + 1;j <= len;j++){
			if(cnt[i] >= 24 && cnt[j] >= 2)
			    ans++;
			if(cnt[i] >= 2 && cnt[j] >= 24)
			    ans++;
			if(cnt[i] >= 14 && cnt[j] >= 4)
			    ans++;
			if(cnt[i] >= 4 && cnt[j] >= 14)
			    ans++;
		}
	}
	for(int i = 1;i <= len;i++){
		for(int j = i + 1;j <= len;j++){
			for(int k = j + 1;k <= len;k++){
				if(cnt[i] >= 4 && cnt[j] >= 4 && cnt[k] >= 2)
				    ans++;
				if(cnt[i] >= 4 && cnt[j] >= 2 && cnt[k] >= 4)
				    ans++;
				if(cnt[i] >= 2 && cnt[j] >= 4 && cnt[k] >= 4)
				    ans++;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V) {
os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
    return os << "(" << P.first << "," << P.second << ")";}

// #define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
typedef long long ll;
typedef double ld;
#define pll pair<ll,ll>
#define pii pair<int, int>
#define pb push_back
#define mp(x, y) make_pair((x), (y))
#define F first
#define S second
#define I insert
#define vi vector<int>
#define vll vector<ll>
#define vpll vector<pll>
#define all(x) (x).begin(), (x).end()
#define sz(x) (ll)(x).size()
   
const ll INF = 1e18 + 7;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    int n ; cin >> n;
    ll Arr[n];
    Arr[0] = 0;
    for(int i = 1 ;i <= n; i++)
        cin >> Arr[i];

    ll dp[n+1][n+1] , pref[n+1];
    for(int i = 0 ;i <= n; i++){
        for(int j = 0 ;j <= n ; j++)
            dp[i][j] = INF;
       
        dp[i][i] = 0;
    }
    pref[0] = 0;
    for(int i = 1 ;i <= n; i++)
        pref[i] = pref[i-1] + Arr[i];
    for(int l = 2 ;l <= n ;l++){
        for(int i = 1 ;i <=n-l+1 ; i++){
            int j = i+l-1;
            for(int k = i ; k < j ; k++){
                dp[i][j] = min(dp[i][j] , pref[j] - pref[i-1] + dp[i][k] + dp[k+1][j]);
            }
            
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}

Measured memory_bytes: 1536
n = int(input())
a = sorted(list(map(int, input().split())))

m = max(a)+1
dp = [1]*m
for i in a:
  if dp[i-1] == 1:
    dp[i-1] = 2 # 整数列にも存在せず、整数列の値の倍数でもない値はすべて"1"のまま
    for j in range(i*2, m, i):
      dp[j-1] = 0
  elif dp[i-1] == 2: # 数列内に複数同じ値がある場合はそれもNGになる
    dp[i-1] = 0

print(sum([1 for i in a if dp[i-1]])) # 判定の対象が"2"であればOK

Measured memory_bytes: 32180
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

#define _USE_MATH_DEFINES

#include <stdio.h>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>
#include <list>
#include <math.h>
#include <map>
#include <iomanip>
#include <functional>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <bitset>

using namespace std;

template<class T> ostream& operator<<(ostream& os, const vector<T>& v) {
	for (auto i = begin(v); i != end(v); i++) os << *i << (i == end(v) - 1 ? "" : " "); return os;
}
template<class T> istream& operator>>(istream& is, vector<T>& v) {
	for (auto i = begin(v); i != end(v); i++) is >> *i; return is;
}

#define MOD 1000000007

bool matrix[1024][1024];
vector<int> edg[1024];
vector<int> color(1024, -1);
int cnts[2];

bool dfs(int i, int is_black)
{
	if (color[i] != -1)
	{
		return color[i] == is_black;
	}
	cnts[is_black]++;
	color[i] = is_black;
	for (int u : edg[i])
	{
		if (!dfs(u, !is_black))
		{
			return false;
		}
	}

	return true;
}

int main() {

#if defined(_DEBUG) 
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

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

	
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		a--, b--;
		matrix[a][b] = 1;
		matrix[b][a] = 1;
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (i == j)
				continue;
			if (!matrix[i][j])
				edg[i].push_back(j);
		}
	}

	bitset<2048> bs;
	bs[1024] = 1;

	for (int i = 0; i < n; i++)
	{
		if (color[i] >= 0)
			continue;
		cnts[0] = cnts[1] = 0;
		if (!dfs(i, 0))
		{
			cout << -1;
			return 0;
		}

		int diff = abs(cnts[0] - cnts[1]);
		bs = (bs << diff) | (bs >> diff);
	}

	int min_resp = n * n;
	for (int i = 0; i < 2048; i++)
	{
		int ii = i - 1024;
		if (!bs[i])
			continue;

		int b = (n - ii) / 2;
		int a = ii + b;

		min_resp = min(min_resp, a * (a - 1) / 2 + b * (b - 1) / 2);
	}

	cout << min_resp;

	return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h> 
 
#define INF (1<<31) - 1 //INT_MAX/2
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using P = std::pair<int, int>;

int main(int argc, char *argv[])
{
    std::string S;
    std::cin >> S;

    bool pre_state = true;
    if (S[0] == 'B') {
        pre_state = true;
    } else if (S[0] == 'W') {
        pre_state = false;
    }

    int ans = 0;
    bool state = true;
    for (int i = 1; i < S.size(); i++) {
        if (S[i] == 'B') {
            state = true;
        } else if (S[i] == 'W') {
            state = false;
        }

        if (pre_state != state) {
            ans++;
        }
        pre_state = state;
    }

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

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

double calc(double dx1, double dy1, double dx2, double dy2) {
    dx1 = (dx1 == -0.0? 0.0: dx1);
    dy1 = (dy1 == -0.0? 0.0: dy1);
    dx2 = (dx2 == -0.0? 0.0: dx2);
    dy2 = (dy2 == -0.0? 0.0: dy2);
    if(dx1 == 0.0 || dx2 == 0.0) {
        return dx1 == dx2 || (dx1 == 0.0 && dy1 == 0.0) || (dx2 == 0.0 && dy2 == 0.0);
    }
    double result = (dy1/dx1) - (dy2/dx2);
    return result < 1e-7 && result > -1e-7 ;
}

int main() {
    int n, i;
    double x1, y1, x2, y2, x3, y3, x4, y4;

    scanf("%d", &n);
    for(i=0; i<n; ++i) {
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf",
              &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);
        if(calc(x2-x1, y2-y1, x4-x3, y4-y3)) {
            printf("YES\n");
        }else {
            printf("NO\n");
        }
    }

    return 0;
}

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


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

 	int a[3];

 	cin >> a[0] >> a[1] >> a[2];

 	sort(a, a+3);

 	do {
 		if (a[0] == a[1] && a[0] != a[2]) {
 			cout << "Yes\n";
 			return 0;
 		}
 	} while (next_permutation(a, a+3));

 	cout << "No\n";
 
    return 0;
}

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

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

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

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

using namespace std;

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

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

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


const int limit = 100010;
int label[limit];

using edge = struct {int to, cost;};
vector<edge> graph[limit];

void add_edge(int from, int to) {
	graph[from].push_back({to, +1});
	graph[to].push_back({from, +2});
}

vector<int> comp[limit];
bool detect = false;

void dfs(int v, int c, int r) {
	comp[r].push_back(v);
	label[v] = c;
	for (auto &e : graph[v]) {
		const int nc = (label[v] + e.cost) % 3;
		if (label[e.to] == -1) dfs(e.to, nc, r);
		if (label[e.to] != nc) detect = true;
	}
}

int main(void) {
	int n, m;
	cin >> n >> m;

	rep(i, m) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		add_edge(a, b);
	}

	fill_n(label, n, -1);

	ll ans = 0LL;

	rep(v, n) {
		if (label[v] != -1) continue;
		detect = false;
		dfs(v, 0, v);
		const int sn = comp[v].size();
		if (detect) {
			ll add = 1LL * sn * sn;
			ans += add;
		} else {
			vector<int> num(3, 0LL);
			int sm = 0;
			for (auto &sv : comp[v]) {
				num[label[sv]]++;
				sm += graph[sv].size();
			}
			sm /= 2;

			if (min({num[0], num[1], num[2]}) == 0)
				ans += sm;
			else
				ans += 1LL * num[0] * num[1] + 1LL * num[1] * num[2] + 1LL * num[2] * num[0];
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 15224
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double

const ld eps = 1e-12;

int n, k;
vector<ld> x, y, c;
void input() {
	cin >> n >> k;
	x.resize(n);
	y.resize(n);
	c.resize(n);
	for (int i = 0; i < n; ++i)
		cin >> x[i] >> y[i] >> c[i];
}

// (px, py)に熱源をセットしたときの所要時間
ld get_time(ld px, ld py) {
	vector<ld> t(n);
	for (int i = 0; i < n; ++i) {
		ld dx = abs(px - x[i]);
		ld dy = abs(py - y[i]);
		ld d = sqrtl(dx * dx + dy * dy);
		t[i] = d * c[i];
	}
	sort(t.begin(), t.end());
	return t[k - 1];
}

// 二円の共有点
tuple<ld, ld, ld, ld> cross_circle(
	ld x1, ld y1, ld r1, ld x2, ld y2, ld r2
) {
	ld dx = abs(x1 - x2);
	ld dy = abs(y1 - y2);
	ld d_center = sqrtl(dx * dx + dy * dy);
	if (d_center < eps)
		return make_tuple(0.0L, 0.0L, 0.0L, 0.0L);
	if (d_center > r1 + r2 + eps)
		return make_tuple(0.0L, 0.0L, 0.0L, 0.0L);
	if (d_center + min(r1, r2) + eps < max(r1, r2))
		return make_tuple(0.0L, 0.0L, 0.0L, 0.0L);
	ld vec_x = y1 - y2, vec_y = x2 - x1;
	ld len = sqrtl(vec_x * vec_x + vec_y * vec_y);
	vec_x /= len, vec_y /= len;
	ld k = (r1 * r1 - r2 * r2 + d_center * d_center) / (2 * d_center);
	ld t = sqrtl(r1 * r1 - k * k);
	ld res_x1 = x1 + k * (x2 - x1) / d_center + t * vec_x;
	ld res_y1 = y1 + k * (y2 - y1) / d_center + t * vec_y;
	ld res_x2 = x1 + k * (x2 - x1) / d_center - t * vec_x;
	ld res_y2 = y1 + k * (y2 - y1) / d_center - t * vec_y;
	return make_tuple(res_x1, res_y1, res_x2, res_y2);
}

// t秒以内で条件を満たせるか
bool judge(ld t) {
	for (int i = 0; i < n; ++i)
		if (get_time(x[i], y[i]) < t + eps)
			return true;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			ld r1 = t / c[i], r2 = t / c[j];
			auto tmp = cross_circle(x[i], y[i], r1, x[j], y[j], r2);
			ld tmpx = get<0>(tmp), tmpy = get<1>(tmp);
			if (get_time(tmpx, tmpy) < t + eps) return true;
			tmpx = get<2>(tmp), tmpy = get<3>(tmp);
			if (get_time(tmpx, tmpy) < t + eps) return true;
		}
	}
	return false;
}

int main() {
	input();
	cout << setprecision(15);
	if (n == 1) {
		cout << 0 << endl;
	}
	else {
		ld ng = 0.0L, ok = 1000000.0L;
		while (ok - ng > eps) {
			ld mid = (ng + ok) / 2;
			if (judge(mid)) ok = mid;
			else ng = mid;
		}
		cout << ok << endl;
	}
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;
 
void Main() {
  int r,g;
  cin >> r >> g;
  int d=g-r;
  g+=d;
  pr(g);
}
 
int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef int64_t ll;
#define rep(i,n) for(int i=1;i<=(int)(n);i++)
ll R,C,K,r,c,v,g[3001][3001],a[3001][3001][4];

int main(){
	cin>>R>>C>>K;
	rep(i,K){cin>>r>>c>>v;g[r][c]=v;}
	rep(i,R)rep(j,C)rep(k,3)a[i][j][k]=max(a[i-1][j][3]+g[i][j],max(a[i][j-1][k-1]+g[i][j],a[i][j-1][k]));
	cout<<a[R][C][3]<<endl;
}


Measured memory_bytes: 355248
def wa(x):
  sum = 0
  fuga = str(x)
  a = len(fuga)
  hoge = list(fuga)
  for i in range(a):
    sum+=int(hoge[i])
  return sum



n = int(input())
min = 114514
for i in range(1,int(n/2)):
  po = wa(i) + wa(n - i)
  if(min > po):
    min = po

if n == 2:
  min = 2
print(min)

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

int main()
{
    int n, k;
    cin >> n >> k;

    vector<ll> a(n);
    for(int i = 0; i < n; ++i)
        cin >> a[i];

    sort(a.begin(), a.end());

    ll res = 0;
    for(int i = n - k - 1; i >= 0; --i)
        res += a[i];

    cout << res << "\n";
    return 0;
}

Measured memory_bytes: 4784
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int a,b,c,x;
    scanf("%d %d %d",&a,&b,&c);
    
    if (a > b){
        x=a;
        a=b;
        b=x;
    }
    if (b > c){
        x=b;
        b=c;
        c=x;
    }
    if (a > b) {
        x=a;
        a=b;
        b=x;
    }
    printf("%d %d %d\n",a,b,c);
    return 0;
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define ALL(a) (a).begin(),(a).end()

using namespace std;
using ll = long long;

const double PI = 3.14159265358979;

void solve()
{
  int c[3][3];
  for(int i = 0; i < 3; ++i)
  {
    cin >> c[i][0];
    cin >> c[i][1];
    cin >> c[i][2];
  }
  int a12 = abs(c[0][0] + c[0][1] + c[0][2] - (c[1][0] + c[1][1] + c[1][2]));
  int a23 = abs(c[1][0] + c[1][1] + c[1][2] - (c[2][0] + c[2][1] + c[2][2]));
  int a13 = abs(c[0][0] + c[0][1] + c[0][2] - (c[2][0] + c[2][1] + c[2][2]));

  int b12 = abs(c[0][0] + c[1][0] + c[2][0] - (c[0][1] + c[1][1] + c[2][1]));
  int b23 = abs(c[0][1] + c[1][1] + c[2][1] - (c[0][2] + c[1][2] + c[2][2]));
  int b13 = abs(c[0][0] + c[1][0] + c[2][0] - (c[0][2] + c[1][2] + c[2][2]));

  if (a12 % 3 + a23 % 3 + a13 % 3 + b12 % 3 + b23 % 3 + b13 % 3 == 0)
    cout << "Yes";
  else cout << "No";
}

int main()
{
  fastio;
  solve();

  return 0;
}

Measured memory_bytes: 3656
import java.util.Scanner;

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

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        int D = sc.nextInt();
        
        int sum;
        
        if (A > B){
            sum = B;
        }else{
            sum = A;
        }
        
        if (C > D) {
            sum += D;
        }else{
            sum += C;
        }
        System.out.println(sum);
    }
    
}


Measured memory_bytes: 21844
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
using namespace std;
using ll = long long;

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main(){
    int n,m;
    set<int> st;
    cin >> n >> m;
    vector<bool> a(n+1);
    for(int i=1;i<=n;i++)   a[i] = true;
    UnionFind tree(n+1);
    for(int i=0;i<m;i++){
        int x,y,z;
        cin >> x >> y >> z;
        tree.unite(x,y);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        st.insert(tree.root(i));
    }
    cout << st.size() << endl;
}

Measured memory_bytes: 5376
MOD = int(input())

if MOD%2 == 0:
  print(-1)
  exit()
if MOD == 7 or MOD == 1:
  print(1)
  exit()
  
def mod(n):         
  return n % MOD

def modpow(a, n):   #mod(a**n)を高速で求める
    res = 1  
    digit = len(str(bin(n))) - 2
    for i in range(digit):
      if (n >> i) & 1:
        res *= mod(a)
        res = mod(res)
      a = mod(a**2)
    return mod(res)
  
res = mod(7)
count = 1

while count <= 10**6:
  res += mod(modpow(10, count)*7)
  res = mod(res)
  count += 1
  if res == 0:
    print(count)
    exit()
    
print(-1)



Measured memory_bytes: 73964
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ff first
#define ss second
// #define mp make_pair
#define pb push_back
// #define pop pop_back
#define all(a) a.begin(), a.end()

const int N = 1e5 + 69;
const ll INF = 1e17;
const ll mod = (ll)1e9 + 7;

ll n, w; 
ll wts[N], val[N];
ll dp[105][N];
// Recursive code without dp meant to get TLE;

ll knapsack(ll n, ll w)
{
    if(n == 0 || w == 0)
        return 0;
    
    if(dp[n - 1][w] > 0)
        return dp[n - 1][w];

    if(wts[n - 1] <= w)
        dp[n - 1][w] = max(val[n - 1] + knapsack(n - 1, w - wts[n - 1]), knapsack(n - 1, w));
    else
        dp[n - 1][w] = knapsack(n - 1, w);
    
    return dp[n - 1][w];
}

void solve()
{
    cin >> n >> w;
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < n; i++)
        cin >> wts[i] >> val[i];
    ll ans = knapsack(n, w);
    cout << ans << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // int t; cin>>t; 
    while(t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 85684
#include <iostream>
#include <algorithm> //min

using namespace std;

int main() {

	int L, R;
	cin >> L >> R;

	//余りは最大でも2018
	int mod_min = 2018;

	//余りは2019周期でパターンが同じなのでRの範囲を縮める
	R = min(R, L + 2019);

	for (int i = L; i < R; i++)
	{
		for (int j = i + 1; j <= R; j++)
		{

			int mod = ((i % 2019) * (j % 2019)) % 2019;
			//cout << mod << "\n";

			if (mod < mod_min) {
				mod_min = mod;
			}
		}
	}

	cout << mod_min;

	return 0;
}

Measured memory_bytes: 256
import sys

result_alphabet = [0] * 26

input_str = sys.stdin.read().lower()

for x in range(len(input_str)):
    alpha_str = input_str[x:x+1]
    alpha_num = ord(alpha_str) - 97
    if alpha_num > -1 and alpha_num < 27:
        result_alphabet[alpha_num] += 1

for i in range(26):
    alphabet = chr(i+97)
    print(f'{alphabet} : {result_alphabet[i]}')


Measured memory_bytes: 5576
#include <iostream>
using namespace std;
int main()
{
    // 整数の入力
    int max_address, c_count, me_address;

    cin >> max_address >> c_count >> me_address;

    int c_address[c_count];

    for(int num = 0; num < c_count; num++) {
        cin >> c_address[num];
    }

    int rise = 0;
    int down = 0;

    for(int s = me_address; s < max_address; s++ ){
        for(int j = 0; j < c_count ; j++) {
            if(c_address[j] == s) {
                rise ++;
            }
        }
    }

    for(int l = me_address; l > 0; l--)
        for(int j = 0; j < c_count ; j++)
            if(c_address[j] == l)
                down ++;

    cout << ((rise > down) ? down : rise );

    return 0;
}

Measured memory_bytes: 256
//
//  second.cpp
//  CoderTest
//
//  Created by yuya on 2019/07/25.
//  Copyright © 2019 yuya. All rights reserved.
//

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
#define all(x) (x).begin(), (x).end()
#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 INF 1000000
#define MOD 998244353



int main()
{
    int A, B, M;
    cin >> A >> B >> M;
    
    vector<int> a(A), b(B);
    
    rep(i, A) {
        cin >> a[i];
    }
    rep(i, B) {
        cin >> b[i];
    }
    
    int price = *min_element(all(a)) + *min_element(all(b));
    
    int x, y, c;
    
    rep(i, M){
        cin >> x >> y >> c;
        x--;
        y--;
        
        int price2 = a[x] + b[y] - c;
        
        price = min(price, price2);
    }
    
    cout << price << endl;
    
    return 0;
}



Measured memory_bytes: 1024
s = input()
found = False
for i,c in enumerate(s[0:len(s)-2]):
    if c == s[i+1]:
        found = True
        print(str(i+1)+" "+str(i+2)) 
        break
    elif c == s[i+2]:
        found = True
        print(str(i+1)+" "+str(i+3))
        break
if found == False:
    if s[len(s)-2] == s[len(s)-1]:
        print(str(len(s)-1)+" "+str(len(s)))
    else:
        print("-1 -1")

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

// TYPEDEF
// ----------------------------------------
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> Pair;
typedef vector<ll> vll;
typedef vector<vector<ll>> Graph;
typedef vector<string> vs;
typedef vector<pair<ll, ll>> Pll;
typedef queue<ll> qll;

// REPEAT
// ----------------------------------------
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REPA(i,a) for(ll i=0;i<(ll)(a.size());i++);
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define COUT(a) cout << (a) << endl;
#define ENDL(a) cout << endl;
#define COUTA(i,a) for(ll i=0;i<(ll)(a.size());i++) {cout << (a)[i] << " ";} cout << endl;

// UTIL
// ----------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define RSORT(a) sort((a).rbegin(), (a).rend())

// DEBUG
// ----------------------------------------
#ifdef _DEBUG
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
#else
#define debug(x)
#endif

template <typename T>
void debugV(const vector<T> v) {
#ifdef _DEBUG
  rep(i, v.size()) {
    cout << i << ":" << v[i] << " ";
  }
  cout << endl;
#else
  (void)v;
#endif
}

// BIT FLAG
// ----------------------------------------
const unsigned int BIT_FLAG_0 = (1 << 0); // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1); // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2); // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3); // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4); // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5); // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6); // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7); // 0000 0000 1000 0000
const unsigned int BIT_FLAG_8 = (1 << 8); // 0000 0001 0000 0000
const unsigned int BIT_FLAG_9 = (1 << 9); // 0000 0010 0000 0000
const unsigned int BIT_FLAG_10 = (1 << 10); // 0000 0100 0000 0000
const unsigned int BIT_FLAG_11 = (1 << 11); // 0000 1000 0000 0000

// CONST
// ----------------------------------------
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr double PI=3.14159265358979323846; // or M_PI
constexpr int MOD = 1000000007;


void Main() {
  ll r;
  cin >> r;
  COUT(r * r);
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}

/*

3 2
*/


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
  
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()


int get_dig_sum(ll x) {
    int s = 0;
    while (x > 0) {
        s += x % 10;
        x /= 10;
    }
    return s;
}

bool is_x_less_than_y(ll x, ll y) {
    return x * get_dig_sum(y) < y * get_dig_sum(x);
}

ll get_num(vector<int> v) {
    ll y = 0;
    reverse(all(v));
    for (int x : v)
        y = y * 10 + x;
    return y;
}

ll f(ll x) {
    vector<int> v;

    while (x > 0) {
        v.push_back(x % 10);
        x /= 10;
    }

    ll ans = -1;

    for (int i = 0; i < v.size(); i++) {
        for (int j = v[i]; j < 10; j++) {
            v[i] = j;

            ll cur = get_num(v);

            if (ans == -1 || is_x_less_than_y(cur, ans)) {
                ans = cur;
            }
        }
    }

    return ans;
}

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

    int k;
    cin >> k;

    ll x = 1;
    while (k--) {
        cout << x << "\n";
        x = f(x + 1);
    }

    return 0;   
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long arr[1000000];
int main()
{
	long long x;
	long double a,b,c,d;
	cin>>x;
	a=x*1.0;
	a=a/3.0;
	a=a*a*a;
	cout<<setprecision(17)<<a<<endl;
}

Measured memory_bytes: 256
sl = list(input())
x,y = map(int,input().split())
lrl = [[],[]]
mode = 0
stack = 0
flag = True
first_t = 0
for s in sl:
    if s == "F":
        stack += 1
    else:
        if flag:
            first_t = stack
            flag = False
        elif stack > 0:
            lrl[mode%2].append(stack)
        mode += 1
        stack = 0
else:
    if flag:
        first_t = stack
        flag = False
    elif stack > 0:
        lrl[mode%2].append(stack)

x = abs(x - first_t)
y = abs(y)
from collections import defaultdict
l = defaultdict(int)
r = defaultdict(int)
l[0] = 1
r[0] = 1
ol = x + sum(lrl[0])
for a in lrl[0]:
    kouho = []
    for ll in l:
        if ll + 2 * a <= ol:
            kouho.append(ll+2*a)
    for i in kouho:
        l[i] = 1

orr = y + sum(lrl[1])
for a in lrl[1]:
    kouho = []
    for rr in r:
        if rr + 2 * a <= orr:
            kouho.append(rr+2*a)
    for i in kouho:
        r[i] = 1


if l[ol] == 1 and r[orr] == 1:
    print("Yes")
    import sys
    sys.exit()

print("No")

Measured memory_bytes: 43740
aa= 0; ab= 0; ac=0
while True :
    edge = map(int, input().split())
    sEdge = sorted(edge)
    a = sEdge[0]
    b = sEdge[1]
    c = sEdge[2]
    if c >= a + b :
        break
    jud = c ** 2 - a ** 2 - b ** 2
    if jud == 0 :
        aa += 1
    elif jud < 0 :
        ab += 1
    else :
        ac += 1
print("{} {} {} {}".format(aa + ab + ac, aa, ab, ac))


Measured memory_bytes: 5596
using System;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(ReadLine());
        string S = ReadLine();
        int ans = 1;
        for(int i = 1; i < N; i++)
        {
            if(S[i] != S[i - 1])
            {
                ans++;
            }
        }
        WriteLine(ans);
    }
}

Measured memory_bytes: 13280
n, y = map(int, input().split())
for i in range(n + 1):
    for j in range(n - i + 1):
        if 10000 * i + 5000 * j + (n - i - j) * 1000 == y:
            print(i, j, n - i - j)
            exit()
print("-1 -1 -1")


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

using namespace std;
int n,ans[5];
string s;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>s;
        if(s=="WA") ans[2]++;
        if(s=="AC") ans[1]++;
        if(s=="TLE") ans[3]++;
        if(s=="RE") ans[4]++;
    }
    for(int i=1; i<=4; i++){
        if(i == 1) cout<<"AC x "<<ans[i]<<'\n';
        if(i == 2) cout<<"WA x "<<ans[i]<<'\n';
        if(i == 3) cout<<"TLE x "<<ans[i]<<'\n';
        if(i == 4) cout<<"RE x "<<ans[i]<<'\n';
    }
}


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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const double EPS = 1e-10;

int main() {
    lint N, K;
    cin >> N >> K;

    lint ans = 0;
    for (int a = 1; a <= N; a++) {
        int a_mod  = a % K;
        int bc_mod = (K - a_mod) % K;

        if ((bc_mod + bc_mod) % K != 0) continue;

        lint cnt = (N - bc_mod) / K + (bc_mod == 0 ? 0 : 1);

        ans += cnt * cnt;
        // d(ans);
    }

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

Measured memory_bytes: 3560
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<list>
#include<map>
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define ll long long

using namespace std;

int n, a;

int main() {
	cin >> n;

	string ans = "APPROVED";
	rep(i, n) {
		cin >> a;
		if (a % 2 == 0) {
			if (!(a % 3 == 0 || a % 5 == 0)) {
				ans = "DENIED";
			}
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define LL long long
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define rf(i,x,y) for(int i=(x);i>=(y);i--)
#define frl(i,x,y) for(int i=(x);i<(y);i++)
using namespace std;
const int N=2022;
const int INF=1e8;
int n,b[N];
char c[N][N];
int a[N][N],f[N][N];
int mn=0;

void read(int &x){
	char ch=getchar();x=0;
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}

int main(){
	//freopen("1.in","r",stdin);
	read(n);
	fr(i,1,n){
		scanf("%s",c[i]+1);
		fr(j,1,n) if (c[i][j]=='1') a[i][j]=f[i][j]=1;
		 else a[i][j]=0,f[i][j]=INF;
	}
	int mn=INF;
	fr(i,1,n)
	 fr(j,1,n)
	  fr(k,1,n){
	  	if (i!=j&&j!=k&&i!=k&&f[j][i]<INF&&f[i][k]<INF&&f[j][k]<INF){
	  		int len=f[j][i]+f[i][k]+f[j][k];
	  		if (len&1) return puts("-1"),0;
	  		mn=min(mn,len);
		}
		f[j][k]=min(f[j][k],f[j][i]+f[i][k]);
	  }
	/*if (mn<INF) cout<<mn/2+1<<endl;
	 else{
	 	int mx=0;
	 	fr(i,1,n)
	 	 fr(j,1,n)
	 	  if (i!=j) mx=max(mx,f[i][j]);
	 	cout<<mx+1<<endl;
	 }*/
	int ans=0;
	fr(i,1,n)
	 fr(j,i+1,n)
	  ans=max(ans,f[i][j]);
	cout<<ans+1<<endl;
	return 0;
}

Measured memory_bytes: 7296
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;

long sgn(long x) { return x > 0 ? 1 : (x < 0 ? -1 : 0); }

long dist_origin(long x, long y) { return abs(x) + abs(y); }

void move_to_dist(long x, long y, long K, long d, vector<long> &xs,
                  vector<long> &ys) {
  const long d0 = dist_origin(x, y);
  const long a = (K - (d - d0)) / 2, b = (K + (d - d0)) / 2;
  if (abs(x) >= a) {
    const long sgn_y = sgn(y) != 0 ? sgn(y) : 1;
    xs.push_back(x - sgn(x) * a);
    ys.push_back(y + sgn_y * b);
  } else if (abs(y) >= a) {
    const long sgn_x = sgn(x) != 0 ? sgn(x) : 1;
    xs.push_back(x + sgn_x * b);
    ys.push_back(y - sgn(y) * a);
  } else {
    assert(false);
  }
  // printf("x = %ld, y = %ld, d = %ld, a = %ld, b = %ld, x1 = %ld, y1 = %ld\n", x,
  //        y, d0, a, b, xs.back(), ys.back());
}

void move_back_to_origin_K(long x, long y, long K, vector<long> &xs,
                           vector<long> &ys) {
  if (dist_origin(x, y) % K != 0) {
    for (long i = xs.size() - 1; i >= 0; i--) {
      printf("%ld %ld\n", xs[i], ys[i]);
    }
    assert(false);
  }

  while (dist_origin(x, y) != K) {
    // printf("(x, y) = (%ld, %ld)\n", x, y);
    if (abs(x) >= abs(y)) {
      x += -K * sgn(x);
    } else {
      y += -K * sgn(y);
    }
    xs.push_back(x);
    ys.push_back(y);
  }
  xs.push_back(0);
  ys.push_back(0);
}

int main(int argc, char *argv[]) {
  // read inputs
  long K, X, Y;
  scanf("%ld %ld %ld", &K, &X, &Y);

  // solve backwards
  vector<long> xs, ys;
  const long d0 = abs(X) + abs(Y);
  const long d0_rounddown = d0 / K * K, d0_roundup = (d0 + K - 1) / K * K;
  xs.push_back(X);
  ys.push_back(Y);

  if (K % 2 == 0 && d0 % 2 == 1) {
    printf("-1\n");
    return 0;
  }

  // move to point where distance to (0, 0) is multiple of K
  if (K % 2 == 0) {
    // make one move beforehand if needed
    if (d0 > 0 && d0 < K) {
      move_to_dist(X, Y, K, d0_roundup, xs, ys);
    }

    // move to point where distance to (0, 0) is d1_rounddown
    const long x = xs.back(), y = ys.back();
    const long d1 = abs(x) + abs(y);
    const long d1_rounddown = d1 / K * K, d1_roundup = (d1 + K - 1) / K * K;
    if (d1 % K != 0) {
      move_to_dist(X, Y, K, d1_rounddown, xs, ys);
    }
  } else {
    // make one move beforehand if needed
    if (d0 < K && d0 % 2 == K % 2) {
      move_to_dist(X, Y, K, K + 1, xs, ys);
    }

    // move to point where distance to (0, 0) is d1_roundown
    const long x = xs.back(), y = ys.back();
    const long d1 = abs(x) + abs(y);
    const long d1_rounddown = d1 / K * K, d1_roundup = (d1 + K - 1) / K * K;
    if (d1 % K != 0) {
      if (d1 % 2 != d1_rounddown % 2) {
        // d1_rounddown if possible
        move_to_dist(x, y, K, d1_rounddown, xs, ys);
      } else {
        // d1_roundup if not
        move_to_dist(x, y, K, d1_roundup, xs, ys);
      }
    }
  }

  // move back to (0, 0)
  move_back_to_origin_K(xs.back(), ys.back(), K, xs, ys);

  printf("%ld\n", (long)xs.size() - 1);
  for (long i = xs.size() - 2; i >= 0; i--) {
    printf("%ld %ld\n", xs[i], ys[i]);
  }

  return 0;
}


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

int main(){
   int N,M;
   cin>>N>>M;
   vector<int> f(N);
   for(int i=0;i<N;i++){
       cin>>f.at(i);
   }
   int sum=INT_MAX;
   for(int i=0;i+M-1<N;i++){
       int left=f.at(i),right=f.at(i+M-1);
       sum=min(sum,min(abs(left),abs(right))+right-left);   
   }
   cout<<sum<<endl;
}

Measured memory_bytes: 768
if __name__ == '__main__':
    N, M = map(int, input().split())
    S = []
    C = []

    for i in range(M):
        s, c = map(int, input().split())
        s -= 1
        S.append(s)
        C.append(c)

    for num in range(0, pow(10, N)):
        st_num = str(num)
        if len(str(st_num))!=N: continue
        cnt = 0
        for m in range(M):
            if int(st_num[S[m]])==C[m]:
                cnt += 1
        if cnt==M:
            print(st_num)
            quit()
    print(-1)


Measured memory_bytes: 9092
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <stdlib.h>

using namespace std;

long int N;
long int power = 1;


int main(){
    cin >> N;

    for(int i = 1;i < N + 1;i++){
        power = power * i % (1000000000 + 7);
    }

    cout << power << endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <list>

using namespace std;

typedef pair<long long int, long long int> P;
typedef pair<P, long long int> PP;
long long int INF = 1e18;
long long int MOD = 1e9 + 7;

#define MAX_V 410000

struct edge{
	int to;
	long long int cost;
};

vector<edge> G[MAX_V];
long long int d[MAX_V];

// 計算コストはO(ElogV)

void shortest_path(int s, int V){ // Vは頂点数
	
	priority_queue<P, vector<P>, greater<P> > que;
	
	for(int i = 0; i < V; i++){
		d[i] = INF;
	}
	d[s] = 0;
	
	que.push(P(0, s));
	
	while(!que.empty()){
		
		P p = que.top();
		que.pop();
		
		int v = p.second;
		
		if(d[v] < p.first){
			continue;
		}
		
		for(int i = 0; i < G[v].size(); i++){
			edge e = G[v][i];
			if(d[e.to] > e.cost + d[v]){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		} // 頂点への最小コストを更新
	}
}

PP node[210000];

int main(){
	
	long long int M, N, K;
	cin >> M >> N >> K;
	
	for(int i = 0; i < K; i++){
		cin >> node[i].first.first >> node[i].first.second;
		node[i].second = i + 1;
	}
	node[K].first.first = M;
	node[K].first.second = N;
	node[K].second = K + 1;
	K++;
	for(int i = 1; i <= K; i++){
		edge e;
		e.cost = 1;
		e.to = i + K;
		G[i].push_back(e);
		e.to = i;
		G[i + K].push_back(e);
	}
	
	sort(node, node + K);
	
	if(node[0].first.first == 1){
		edge e;
		e.cost = node[0].first.second - 1;
		e.to = node[0].second;
		G[0].push_back(e);
	}
	
	for(int i = 0; i < K - 1; i++){
		if(node[i].first.first == node[i + 1].first.first){
			edge e;
			e.cost = node[i + 1].first.second - node[i].first.second;
			e.to = node[i + 1].second;
			G[node[i].second].push_back(e);
			e.to = node[i].second;
			G[node[i + 1].second].push_back(e);
			
		}
	}
	
	for(int i = 0; i < K; i++){
		swap(node[i].first.first, node[i].first.second);
		node[i].second += K;
	}
	
	sort(node, node + K);
	
	for(int i = 0; i < K - 1; i++){
		if(node[i].first.first == node[i + 1].first.first){
			edge e;
			e.cost = node[i + 1].first.second - node[i].first.second;
			e.to = node[i + 1].second;
			G[node[i].second].push_back(e);
			e.to = node[i].second;
			G[node[i + 1].second].push_back(e);
			
		}
	}
	
	shortest_path(0, 2 * K + 1);
	
	long long int ans = min(d[K], d[2 * K]);
	
	if(ans == INF){
		cout << -1 << endl;
	}else{
		cout << ans << endl;
	}
	
	return 0;
}


Measured memory_bytes: 54816
#include <bits/stdc++.h>
using namespace std;
vector<int> v[3000];
set<int> se,se2;

void dfs(int x) {
  if(!v[x].size()) {
    se.insert(x);
    return;
  }
  if(se2.count(x)) return;
  se2.insert(x);
  for(int i=0; i<v[x].size(); i++) dfs(v[x][i]);
}

int main() {
  int n;
  while(cin >> n && n) {
    for(int i=0; i<3000; i++) v[i].clear();
    se.clear();se2.clear();
    map<string,int> m;
    for(int l=0; l<n; l++) {
      string s;
      cin >> s;
      string t="";
      int k=0;
      int x=-1;
      for(int i=0; i<s.size(); i++) {
        if(!isalpha(s[i])) {
          t=s.substr(k,i-k);
          k=i+1;
          if(!m.count(t)) {
            int c=m.size();
            m[t]=c;
          }
          if(x==-1) {
            x=m[t];
            continue;
          }
          v[x].push_back(m[t]);
        }
      }
    }
    dfs(0);
    cout << se.size() << endl;
  }
  return 0;
}


Measured memory_bytes: 1484
while True:
	x, y, s = map(int, input().split())
	if x == 0: break
	ans = 0
	for p1 in range(1, s+1):
		for p2 in range(p1, s+1):
			t = p1 + p2 + (p1*x)//100 + (p2*x)//100
			if t > s: break
			if t != s: continue
			t = p1 + p2 + (p1*y)//100 + (p2*y)//100
			if t > ans: ans = t
	print(ans)


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

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

    int N;
    cin >> N;
    vector<P> lis;
    for (int i = 0; i < N; i++) {
        ll a, b; cin >> a >> b;
        lis.push_back(P(b, a));
    }

    sort(lis.begin(), lis.end());

    ll pre = 0;
    for (int i = 0; i < N; i++) {
        if (pre+lis.at(i).second > lis.at(i).first) {
            cout << "No" << endl;
            return 0;
        }
        pre += lis.at(i).second;
    }

    cout << "Yes" << endl;
    return 0;
}

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


int six[10],nine[10];

typedef struct point
{
	int v, cnt;
}point;

bool vis[100005];

int main()
{
	
	int n;
	int lens,lenn;
	for(int i=1;pow(6,i)<=100000;i++)
	{
		six[i] = pow(6,i);
		lens = i;

	}
	for(int i=1;pow(9,i)<=100000;i++)
	{
		nine[i] = pow(9,i);
		lenn = i;
	}

	nine[0] = six[0] = 0;
	while(cin>>n)
	{
		/*
		int tot = 0;
		while(n>=6)
		{
			int pos1 = upper_bound(nine,nine+1+lenn,n) - nine;
			n-=nine[pos1-1];
			//cout<<nine[pos1-1]<<" ";
			if(pos1-1 !=0) tot++;
			int pos2 = upper_bound(six,six+1+lens,n) - six;
			n-=six[pos2-1];
			//cout<<six[pos2-1]<<" ";
			if(pos2-1 !=0) tot++;
			cout<<n<<"\n";
		 } 
		cout<<tot+n<<"\n";
		*/
		memset(vis,0,sizeof(vis));
		deque<point>q;
		q.push_back({n,0});
		while(!q.empty())
		{
			point p = q.front();
			q.pop_front();
			if(p.v==0)
			{
				cout<<p.cnt<<"\n";
				break;
			 } 
			int tmp;
			tmp=p.v-1;
			if(tmp>=0 && !vis[tmp])
			{
				vis[tmp] = 1;
				q.push_back({tmp,p.cnt+1});
			}
			tmp=p.v-pow(6,1);
			if(tmp>=0 && !vis[tmp])
			{
				vis[tmp] = 1;
				q.push_back({tmp,p.cnt+1});
			}
			tmp=p.v-pow(6,2);
			if(tmp>=0 && !vis[tmp])
			{
				vis[tmp] = 1;
				q.push_back({tmp,p.cnt+1});
			}
			tmp=p.v-pow(6,3);
			if(tmp>=0 && !vis[tmp])
			{
				vis[tmp] = 1;
				q.push_back({tmp,p.cnt+1});
			}
			tmp=p.v-pow(6,4);
			if(tmp>=0 && !vis[tmp])
			{
				vis[tmp] = 1;
				q.push_back({tmp,p.cnt+1});
			}
			tmp=p.v-pow(6,5);
			if(tmp>=0 && !vis[tmp])
			{
				vis[tmp] = 1;
				q.push_back({tmp,p.cnt+1});
			}
			tmp=p.v-pow(6,6);
			if(tmp>=0 && !vis[tmp])
			{
				vis[tmp] = 1;
				q.push_back({tmp,p.cnt+1});
			}
			tmp=p.v-pow(9,1);
			if(tmp>=0 && !vis[tmp])
			{
				vis[tmp] = 1;
				q.push_back({tmp,p.cnt+1});
			}
			tmp=p.v-pow(9,2);
			if(tmp>=0 && !vis[tmp])
			{
				vis[tmp] = 1;
				q.push_back({tmp,p.cnt+1});
			}
			tmp=p.v-pow(9,3);
			if(tmp>=0 && !vis[tmp])
			{
				vis[tmp] = 1;
				q.push_back({tmp,p.cnt+1});
			}
			tmp=p.v-pow(9,4);
			if(tmp>=0 && !vis[tmp])
			{
				vis[tmp] = 1;
				q.push_back({tmp,p.cnt+1});
			}
			tmp=p.v-pow(9,5);
			if(tmp>=0 && !vis[tmp])
			{
				vis[tmp] = 1;
				q.push_back({tmp,p.cnt+1});
			}
		}
		
	}
}

Measured memory_bytes: 512
n, m = gets.split.map(&:to_i)
abs = n.times.map { gets.split.map(&:to_i) }.sort_by { |a, b| a }

ans = 0

abs.each do |a, b|
  if b >= m
    ans += a * m
    break
  end

  ans += a * b
  m -= b
end

puts ans


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

ll gcd(ll a, ll b){
  if(b == 0){
    return a;
  }
  else{
    return gcd(b,(a%b));
  }
}
ll lcm(ll a,ll b){
  return a/gcd(a,b)*b;
}

int main(){
  vector<int> vec(3);
  for(int i=0;i<3;i++){
    cin>>vec.at(i);
  }
  sort(vec.begin(),vec.end());
  if(vec.at(0)==vec.at(1)&&vec.at(1)!=vec.at(2)){
    cout<<"Yes"<<endl;
    return 0;
  }
  if(vec.at(0)!=vec.at(1)&&vec.at(1)==vec.at(2)){
    cout<<"Yes"<<endl;
    return 0;
  }
  cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
const int INF = 1e9;


int main(){
  int n;
  while(1){
    cin>>n;
    if(n==0){
      break;
    }
    vector<int> a(n);
    for(int i=0;i<n;i++){
      cin>>a[i];
    }
    sort(a.begin(),a.end());
    a.erase(a.end()-1);
    a.erase(a.begin());
    int sum=0;
    for(int i=0;i<a.size();i++){
      sum+=a[i];
    }
    cout<<sum/a.size()<<endl;
  }
  return 0;
}



Measured memory_bytes: 3160
#include<stdio.h>
#include<string.h>
#define LEN 100005

typedef struct pp{
  char name[100];
  int t;
}P; //構造体の定義

P Q[LEN];

int head;
int tail;
int n;
void enqueue(P x){
  Q[tail]=x;
  tail = (tail+1)%LEN; //LENで巡回させる。
}

P dequeue(){
  P x = Q[head]; //先頭を取り出す。
  head = (head+1)%LEN;
  return x;
}

int min(int a, int b){
  return a<b? a:b;
}//a<bが真ならa 偽ならbを返す。

int main(){
  int elaps =0,c;
  int i,q;
  P u; //取り出す構造体避難用
  scanf("%d %d",&n,&q); //nはプロセスの数　qはクオンタム
  for (i = 1; i <= n; i++) { //i=1は仕様　別に0でも動く?
    scanf("%s",Q[i].name );
    scanf("%d",&Q[i].t);
  }
  head=1;
  tail = n+1;
  //simu
  while(head!=tail) //head=tail になったときシミュレーション終了
  {
    u = dequeue();
    c = min(u.t,q);
    u.t-=c;
    elaps += c; //経過時間
    if(u.t>0)enqueue(u);
    else{
      printf("%s %d\n",u.name,elaps );//終わったら表示
    }
  }
return 0;
}



Measured memory_bytes: 11876
X,Y=map(int,input().split())
n=int(Y/2)
check=0
if 2 * X == Y:
    check = 1
elif 4 * X == Y:
    check = 1
else:
    for i in range(n):
        #print("i=",i,"n=",n)
        if ( (2*(i+1) + 4*(X-i-1)) == Y ):
            check=1
            break
if check==1:
    print("Yes")
else:
    print("No")

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

int main() {

	int h, w; cin >> h >> w;
	vector<vector<char>> a(h + 2, vector<char>(w + 2, 'e'));
	for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) {
		cin >> a[i][j];
	}
	int ans = 0;
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {

			// BFS のためのデータ構造
			vector<vector<int>> dist(h + 2, vector<int>(w + 2, -1)); // 全頂点を「未訪問」に初期化
			queue<pair<int, int>> que;

			int sy = i;
			int sx = j;

			if (a[sy][sx] == '#') continue;

			// 初期条件
			dist[sy][sx] = 0;
			que.push({ sy,sx });
			const int dy[4] = { 1, 0, -1, 0 };
			const int dx[4] = { 0, 1, 0, -1 };

			// BFS 開始 (キューが空になるまで探索を行う)
			while (!que.empty()) {

				pair<int, int> p = que.front(); // キューから先頭頂点を取り出す
				que.pop();

				// p から辿れるマスをすべて調べる
				for (int i = 0; i < 4; i++) {

					int y_next = p.first + dy[i];
					int x_next = p.second + dx[i];

					if (dist[y_next][x_next] != -1) continue;
					if (a[y_next][x_next] == 'e' || a[y_next][x_next] == '#') continue;

					// 新たなマス { y_next, x_next } について距離情報を更新してキューに追加する
					dist[y_next][x_next] = dist[p.first][p.second] + 1;
					que.push({ y_next, x_next });

				}

			}
			for (int y = 1; y <= h; y++) {
				for (int x = 1; x <= w; x++) {
					ans = max(ans, dist[y][x]);
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

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

#ifdef BTK
#include<dvector.h>
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww{cww(){
    CIN_ONLY{
        ios::sync_with_stdio(false);cin.tie(0);
    }
}}star;
#define DEBUG if(0)
#endif

#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l,T r)
{bool a=l>r;if(a)l=r;return a;}
template <typename T>inline bool chmax(T &l,T r)
{bool a=l<r;if(a)l=r;return a;}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}

LL dm[41234];
LL nt[41234];
LL ceil(LL a,LL b){
    return (a+b-1)/b;
}
typedef vector<int> V;
int main(){
    int n;
    LL hh,aa,dd,ss;
    cin>>n>>hh>>aa>>dd>>ss;
    LL ret=0;
    REP(i,n){
        int h,a,d,s;
        cin>>h>>a>>d>>s;
        if(aa-d<=0&&a-dd>0){
            cout<<-1<<endl;
            return 0;
        }
        if(a-dd<=0){
            i--;
            n--;
            continue;
        }
        dm[i]=a-dd;
        nt[i]=ceil(h,aa-d);
        if(ss<s)ret+=dm[i];
    }
    V v(n);
    iota(ALL(v),0);
    sort(ALL(v),
         [&](const int i,const int j){
             LL dij=dm[i]*(nt[i]-1)+dm[j]*(nt[i]+nt[j]-1);
             LL dji=dm[j]*(nt[j]-1)+dm[i]*(nt[i]+nt[j]-1);
             return dij<dji;
         }
         );
    LL turn=0;
    for(auto &i:v){
        DEBUG cout<<i<<" "<<dm[i]<<" "<<nt[i]<<endl;
        turn+=nt[i];
        ret+=dm[i]*(turn-1);
        if(ret>=hh){
            cout<<-1<<endl;
            return 0;
        }
    }
    cout<<ret<<endl;
    
    return 0;
}

Measured memory_bytes: 3696