akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main()
{
    int K, A, B;
    cin >> K >> A >> B;

    if (A + 2 >= B)
    {
        cout << K + 1 << endl;
        return 0;
    }

    long long ans = 1;
    while (K > 0)
    {
        if (ans >= A)
        {
            if (K >= 2)
            {
                ans += (long long)B - A;
                K -= 2;
            }
            else
            {
                ans += K;
                break;
            }
        }
        else if (ans < A)
        {
            if (K >= A - ans + 2)
            {
                K -= (A - ans) + 2;
                ans += (long long)B - ans;
            }
            else
            {
                ans += K;
                break;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#define  INF 1000000
using namespace std;


int main(void){
	int n;
	int ptime,ctimes;
	int pdis,cdis;
	while(cin >> n,n){
		int dp[41][3];
		for(int i=0;i<41;i++)
			for(int j=0;j<3;j++)
				dp[i][j]=INF;
		dp[0][0]=0;
		cin >> pdis >> ptime;
		if(pdis<= ptime)
			dp[1][0]=pdis;
		cdis=pdis,ctimes=ptime;
		for(int i=2;i<=n;i++){
			cin >> cdis >> ctimes;
			for(int j=0;j<2;j++){
				if( abs(cdis-pdis)*(j+2.0) <= (ctimes-ptime))
					dp[i][j+1]=min(dp[i][j+1],dp[i-1][j]+abs(cdis-pdis));
			}
			for(int j=0;j<3;j++){
				if( (j+2)*pdis+cdis <= (ctimes-ptime) )
					dp[i][0]=min(dp[i][0],dp[i-1][j]+cdis+pdis);
			}
			pdis=cdis;
			ptime=ctimes;
		}

		int ans=INF;
		for(int i=0;i<3;i++)
			ans=min(ans,dp[n][i]);
		if(ans!=INF){
			ans+=cdis;
			cout << "OK " << ans << endl;
		}else{
			for(int i=n-1;i>=0;i--)
				for(int j=0;j<3;j++)
					if(dp[i][j]!=INF)
						cout << "NG " << i+1 << endl,j=4,i=-1;
		}
	/*	for(int i=0;i<=4;i++){
			for(int j=0;j<3;j++)
				cout << (j?" ":"") << dp[i][j];
			cout  << endl;
		}*/
	}
	return 0;
}

Measured memory_bytes: 1160
import java.util.Scanner;

public class Main {

    private static int m;
    private static String[][] a;
    private static String[][] b;

    private static boolean matched(int posx, int posy) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (!a[posx + i][posy + j].equals(b[i][j])) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        m = sc.nextInt();
        a = new String[n][n];
        b = new String[m][m];
        for (int i = 0; i < n; i++) {
            String[] sa = sc.next().split("");
            for (int j = 0; j < n; j++) {
                a[i][j] = sa[j];
            }
        }
        for (int i = 0; i < m; i++) {
            String[] sb = sc.next().split("");
            for (int j = 0; j < m; j++) {
                b[i][j] = sb[j];
            }
        }

        for (int i = 0; i < n - m + 1; i++) {
            for (int j = 0; j < n - m + 1; j++) {
                if (matched(i, j)) {
                    System.out.println("Yes");
                    return;
                }
            }
        }
        System.out.println("No");
    }

}


Measured memory_bytes: 21972
(defpackage :abc-167-d
  (:use :cl)
  (:shadow :search))
(in-package :abc-167-d)

(defun set-path (from table to)
  (unless (gethash from table)
    (setf (gethash from table) ()))
  (setf (gethash from table) (cons to (gethash from table))))

(defun get-path (from table)
  (gethash from table))

(defun set-mark (mark marks room)
  (if (= 0 (aref marks room))
      (setf (aref marks room) mark)))

(defun get-mark (marks room)
  (aref marks room))

(let* ((n (read))
       (m (read))
       (-> (make-hash-table :size (1+ n)))
       (at (make-array `(,(1+ n)) :initial-element 0)))
  ;; read
  (loop :for i :from 1 :to m
        :do (let ((ai (read))
                  (bi (read)))
              (set-path ai -> bi)
              (set-path bi -> ai)))
  (labels ((search (rooms)
             (loop :for current :in rooms
                   :append (loop :for room :in (get-path current ->)
                                 :if (set-mark current at room)
                                 :collect room))))
    ;; search
    (loop :for rooms := (search (if rooms rooms (list 1)))
          :while rooms)
    ;; TODO
    (block finally
      (loop :for i :from 2 :to n
            :if (= (get-mark at i) 0)
            :do (progn
                  (format t "No~%")
                  (return-from finally)))
      (format t "Yes~%")
      (loop :for i :from 2 :to n
            :do (format t "~A~%" (get-mark at i))))))


Measured memory_bytes: 86824
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
typedef long long ll;
long long mod = 1e9 + 7;
const long long INF = 1LL << 60;
using namespace std;

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

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

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n), b(n), c(n);
    rep(i, n)
    {
        cin >> a[i];
    }

    rep(i, n)
    {
        cin >> b[i];
    }

    rep(i, n)
    {
        cin >> c[i];
    }

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

    ll ans = 0;

    rep(i, n)
    {
        ll a_num = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
        ll c_num = c.end() - upper_bound(c.begin(), c.end(), b[i]);

        ans += a_num * c_num;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}

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

	for(int len = min(s.size(), t.size()); len >= 0; len--){
		set<vector<int>> st;

		vector<int> cnt(26,0);
		int i = 0;
		while(i < len){
			cnt[ s[i++] - 'a' ]++;
		}
		st.emplace(cnt);
		while(i < s.size()){
			cnt[ s[i] - 'a' ]++;
			cnt[ s[i - len] - 'a' ]--;
			st.emplace(cnt);
			i++;
		}

		cnt = vector<int>(26,0);
		i = 0;
		while(i < len){
			cnt[ t[i++] - 'a' ]++;
		}
		if(st.count(cnt)){
			cout << len << endl;
			return 0;
		}

		while(i < t.size()){
			cnt[ t[i] - 'a' ]++;
			cnt[ t[i - len] - 'a' ]--;
			if(st.count(cnt)){
				cout << len << endl;
				return 0;
			}
			i++;
		}
	}
	cout << 0 << endl;
}



Measured memory_bytes: 3904
N = int(input())
X = list(map(int,input().split()))

X.sort()

Xmin = min(X)
Xmax = max(X)

#print(Xmin,Xmax)

T =[]

for i in range(1,101):
    HP = 0
    for j in X:
        HP = HP + (i-j)**2
    T.append(HP)
print(min(T))

Measured memory_bytes: 3064
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <set>
#include <map>
#include <complex>
#include <iomanip>
#include <cmath>
using namespace std;
typedef long long ll;

int main()
{
  int n;
  cin >> n;
  cout << n * 800 - n / 15 * 200 << endl;
}

Measured memory_bytes: 256
N = int(input())
S = list(input())
ans = 0
for i in range(1, N):
    # print('S', S[:i], S[i:])
    X = set(S[:i])
    Y = set(S[i:])
    # print('X & Y', X & Y)
    ans = max(ans, len(X & Y))
print(ans)


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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

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

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

    ll N, M;
    cin >> N >> M;

    vector<bool> flags(N+1, false);
    rep (i, M) {
        ll a;
        cin >> a;
        flags[a] = true;
    }

    vector<ll> dp(N+1, 0);
    dp[N] = 1;
    for (ll i = N-1; i >= 0; i--) {
        if (flags[i]) {
            dp[i] = 0;
            continue;
        }
        if (i == N-1) {
            dp[i] = dp[i+1];
        } else {
            dp[i] = (dp[i+1] + dp[i+2]) % MOD;
        }
    }

    cout << dp[0] << endl;
    return 0;
}

Measured memory_bytes: 1024
package main

import "fmt"

func main() {
	var N int
	fmt.Scan(&N)
	C := make([]int, N-1)
	S := make([]int, N-1)
	F := make([]int, N-1)
	for i := 0; i < N-1; i++ {
		fmt.Scan(&C[i])
		fmt.Scan(&S[i])
		fmt.Scan(&F[i])
	}
	for i := 0; i < N-1; i++ { // 駅0~N-2まで(0-indexed)
		// 駅iを何時に出発できるか？ S[i]+xF[i] >= now を満たす最小のxを求める。
		// nowを更新する
		now := S[i] + C[i]
		// fmt.Printf("i %d, now %d\n", i, now)
		for j := i + 1; j < N-1; j++ { // 駅iからN-2駅まで
			// 時刻nowで、j駅にいる
			// 次に出発できるのは何時か？
			x := 0
			for {
				if S[j]+x*F[j] >= now {
					break
				}
				x++
			}
			now += (S[j] + x*F[j] - now) + C[j]
			// fmt.Printf("i %d, j %d, x %d, now %d\n", i, j, x, now)
		}
		fmt.Println(now)
	}
	fmt.Println(0)
}


Measured memory_bytes: 640
#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import sys

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n = int(input())
    d = list(map(int,ipti().split()))
    ans = 0

    for i in range(n-1):
        for j in range(i+1, n):
           ans += d[i] * d[j]

    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
const int md=998244353;
int f[302][302][702][4],r;
int n,m,i,j,k1,lst,cur,s0,s1;
char s[302];
int main() {
  scanf("%s",s);  n=strlen(s);
  scanf("%d",&m); m=min(m,n);
  f[0][0][0][0]=1;
  for (i=0; i<n; i++) {
    cur=s[i]-'0';
	for (j=0; j<=m; j++) for (k1=0; k1<=i+j; k1++) for (lst=0; lst<4; lst++) if (f[i][j][k1][lst]) {
	  if (cur==0) {
	    f[i+1][j][k1][0]=(f[i+1][j][k1][0]+f[i][j][k1][lst])%md;
		if (lst<2) f[i][j+1][k1+1][1]=(f[i][j+1][k1+1][1]+f[i][j][k1][lst])%md;
	  } else {
	    f[i+1][j][k1][(lst/2)*2+1]=(f[i+1][j][k1][(lst/2)*2+1]+f[i][j][k1][lst])%md;
		if (k1>0 && lst%2==0) f[i+1][j][k1-1][2]=(f[i+1][j][k1-1][2]+f[i][j][k1][lst])%md;
	  }
    }
  }
  for (j=0; j<=m; j++) for (lst=0; lst<4; lst++) r=(r+f[n][j][0][lst])%md;
  printf("%d\n",r);
  return 0;
}


Measured memory_bytes: 444912
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<iomanip>
using namespace std;

int main() {
    cout << fixed << setprecision(15);
    int N; cin >> N;
    vector<int> X(N), Y(N), index(N);
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i];
        index[i] = i;
    }

    double sum = 0;
    int cnt = 0;
    do {
        cnt++;
        for (int i = 1; i < N; i++) {
            int j = index[i];
            int k = index[i - 1];
            sum += sqrt((X[j] - X[k]) * (X[j] - X[k]) + (Y[j] - Y[k]) * (Y[j] - Y[k]));
        }
    } while (next_permutation(index.begin(), index.end()));

    cout << sum / cnt << endl;
}


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

using namespace std;
typedef long long int ll;
typedef long double ld;
#define REP(i, n) for(ll i = 0LL; i < (ll)(n); i++)
#define REPR(i, n) for (ll i = (ll)(n) - 1; i >= 0; i--)
#define FOR(i, n, m) for(ll i = (ll)n; i < (ll)(m); i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1LL << 62)

#define PI (acos(-1))
#define PRINT(x) cout << x << endl
 
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll countDigit(ll n) { return floor(log10(n) + 1); } 
typedef pair <ll,ll> P;
static const ll dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};

template <typename T> 
ostream& operator<<(ostream& os, const vector<T>& v) 
{ 
    for (int i = 0; i < (int)v.size(); ++i) os << v[i] << " ";  
    return os; 
}

template <typename T1, typename T2> 
ostream& operator<<(ostream& os, const map<T1, T2>& m) 
{ 
    for (auto p : m) os << "<" << p.first << ", " << p.second << "> "; 
    return os; 
}

struct UnionFind {
    vector<ll> par;
    vector<ll> sz;
 
    UnionFind(ll n=0){ if(n>0) initialize(n); }
    void initialize(ll n){
        par.resize(n);
        sz.assign(n, 1);
        for(ll i=0; i<n; i++){
            par[i] = i;
        }
    }
 
    ll find(ll x){
        if(par[x] == x){
            return x;
        }else{
            return par[x] = find(par[x]);
        }
    }
 
    bool unite(ll x, ll y){
        x = find(x), y = find(y);
        if(x == y) return false;
        if(sz[x] > sz[y]) swap(x, y);
        par[x] = y;
        sz[y] += sz[x];
        return true;
    }
 
    bool same(ll x, ll y){ return find(x) == find(y); }
    ll size(ll x){ return sz[find(x)]; }
};

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

    UnionFind uf(N);
    vector<set<ll>> graph(N);
    REP(i, M) {
        ll A, B;
        cin >> A >> B;
        A--; B--;
        uf.unite(A, B);
        graph[A].insert(B);
        graph[B].insert(A);
    }
    REP(i, K) {
        ll C, D;
        cin >> C >> D;
        C--; D--;
        if (uf.same(C, D)) {
            graph[C].insert(D);
            graph[D].insert(C);
        }
    }
    REP(i, N) {
        cout << uf.size(i) - graph[i].size() - 1 << " ";
    }
    cout << endl;
    return 0;
} 

Measured memory_bytes: 25856
// Equation
import java.util.*;

public class Main {
	static int pos;
	static String equation;
	static int a, b, c, d, e, f, g, h, i, j, k;

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			equation = scanner.next();
			if (equation.equals("#"))
				break;
			boolean result = true;
			out: for (a = 0; a < 2; a++)
				for (b = 0; b < 2; b++)
					for (c = 0; c < 2; c++)
						for (d = 0; d < 2; d++)
							for (e = 0; e < 2; e++)
								for (f = 0; f < 2; f++)
									for (g = 0; g < 2; g++)
										for (h = 0; h < 2; h++)
											for (i = 0; i < 2; i++)
												for (j = 0; j < 2; j++)
													for (k = 0; k < 2; k++) {
														pos = 0;
														result = result
																&& eval();
														if (!result)
															break out;
													}
			if (result)
				System.out.println("YES");
			else
				System.out.println("NO");
		}
		scanner.close();
	}

	static boolean eval() {
		boolean boola = formura();
		pos++;
		boolean boolb = formura();
		return boola == boolb;
	}

	static boolean formura() {
		char cha = equation.charAt(pos);
		pos++;
		switch (cha) {
		case 'T':
			return true;
		case 'F':
			return false;
		case 'a':
			return a == 1;
		case 'b':
			return b == 1;
		case 'c':
			return c == 1;
		case 'd':
			return d == 1;
		case 'e':
			return e == 1;
		case 'f':
			return f == 1;
		case 'g':
			return g == 1;
		case 'h':
			return h == 1;
		case 'i':
			return i == 1;
		case 'j':
			return j == 1;
		case 'k':
			return k == 1;
		case '-':
			return !formura();
		case '(':
			boolean boola = formura();
			char chb = equation.charAt(pos);
			pos++;
			boolean boolb;
			switch (chb) {
			case '*':
				boolb = formura();
				pos++;
				return boola && boolb;
			case '+':
				boolb = formura();
				pos++;
				return boola || boolb;
			case '-':
				pos++;
				boolb = formura();
				pos++;
				return !boola || boolb;
			}
		}
		return false;
	}
}

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

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    
    if(a<b){
        if(b<c){
            cout << "Yes" << endl;
        }else{
          cout << "No" << endl;  
        }
    }else{
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3092
///                                                     ببِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم
#include <bits/stdc++.h>
#define off  exit( 0 )
#define cn   continue
#define rt   return
#define sc   scanf
#define pr   printf
#define pb   push_back
#define pf   push_front
#define p_f  pop_front
#define p_b  pop_back
#define ff   first
#define ss   second
#define vec  vector
#define gcd  __gcd
#define pi   acos( -1 )
#define ll   long long
#define ld   long double
#define N    300256
#define M    1000000007
#define I    1000000000000000000
#define pdd  pair < ld, ld >
#define pll  pair < ll, ll >
#define pii  pair < int, int >
#define rep( a, b, c, d )  for( int a = b; a <= c; a += d )
#define rvv( a, b, c, d )  for( int a = b; a >= c; a -= d )
#define en                 printf( "\n" )
#define sqr( a )           a * a
#define all( c )           c.begin(), c.end()
#define srt( c )           sort( all( c ) )
#define rev( c )           reverse( all( c ) )
#define srtr( c )          sort( c.rbegin(), c.rend() )
#define numcounts          __builtin_popcount
#define mxn( x, y, z )     max( x, min( y, z ) )
#define mnx( x, y, z )     min( x, max( y, z ) )
const int dx[ ] = { 1, -1, 0, 0 };
const int dy[ ] = { 0, 0, -1, 1 };
using namespace std;
ll ttt = 1;
ll n, k, w[N], v[N], dp[N];
void solve()
{
    cin >> n >> k;
    for( ll i = 1; i <= n; i ++ )
        cin >> w[i] >> v[i];
    dp[0] = 0;
    for( ll i = 1; i <= n; i ++ )
    {
        for( ll j = k; j > 0; j -- )
        {
            if(j - w[i] >= 0 )dp[j] = max( dp[j], dp[j-w[i]] + v[i] );
        }
    }
    cout << dp[k];

}
int main()
{
    //sc( "%I64d", &ttt );
    for( int i = 0; i < ttt; i ++ )
        solve();
}














Measured memory_bytes: 5120
// C.

#include <iostream>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[])
{
	int n, a, ans = 0;
	cin >> n;
	for (int i = 0; i <= n; ++i) {
		cin >> a;
		while ((a % 2) == 0) {
			++ans;
			a /= 2;
		}
	}
	cout << ans << endl;
	return 0;
}


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

int main() {
    string s;
    cin >> s;
    int x = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '1'){
            x++;
        }
    }
    cout << x << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e18
int main(){

	ll a,b,c,k;
	cin>>a>>b>>c>>k;

	if(k%2==0){
		cout<<a-b<<endl;
	}
	else{
		cout<<b-a<<endl;
	}

	

}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
	int n,x;
	int small = 10001,big = -1;
	cin>>n;
	for(int i = 0;i < n;i++){
		cin>>x;
		if(x <= small)small = x;
		if(x >= big)big = x;
	}
	
	cout<<big-small<<endl;
	
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());

		int best = 0;
		int ren = 0;
		for (int i = 0; i < n; i++) {
			long a = Long.parseLong(sc.next());
			long b = Long.parseLong(sc.next());
			ren = (a == b) ? (ren + 1) : (0);

			if (best <= ren) {
				best = ren;
			}
		}

		System.out.println(best >= 3 ? "Yes" : "No");
	}
}

Measured memory_bytes: 35616
#include<bits/stdc++.h>
#define long long long
using namespace std;
const int N=1e5,inf=1e9;
vector<string>v;
void gen(string s)
{
  if(s.size()==3)
  {
    v.push_back(s);return ;
  }
  for(char i='0';i<='9';i++)
  {
    s.push_back(i);gen(s);
    s.pop_back();
  }
}
int dp[N+2][3];
bool cal(string s,string a)
{
  //cout<<a<<endl;
  int n=s.size();
  for(int i=1;i<=n;i++)
  {
    dp[i][2]=dp[i-1][2];dp[i][1]=dp[i-1][1];dp[i][0]=dp[i-1][0];
    if(s[i-1]==a[2])dp[i][2]|=dp[i-1][1];
    if(s[i-1]==a[1])dp[i][1]|=dp[i-1][0];
    if(s[i-1]==a[0])dp[i][0]=1;

    if(dp[i][2])return true;
  }
  return false;
}
int main()
{
  ios_base::sync_with_stdio(0);cin.tie(0);
  int n;cin>>n;string s;gen(s);cin>>s;

  //cal(s,"022");exit(0);
  int ans=0;
  for(auto x:v)ans+=cal(s,x);
  cout<<ans<<endl;
  
  return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const ll M = 1000000007;
ll n, k;
ll d[100005];
ll ans;

ll f(ll p, ll q)
{
    if(q == 0) return 1;
    ll t = f(p, q / 2);
    if(q % 2 == 0) return t * t % M;
    else return t * t % M * p % M;
}

int main()
{
    scanf("%lld%lld", &n, &k);
    for(ll i = 1; i <= k; i++)
    {
        ll t = (d[i] + i) % M;
        ll t2 = f(k / i, n);
        ans += t * t2 % M;
        ans %= M;
        for(ll j = i * 2; j <= k; j += i) d[j] += M - i - d[i], d[j] %= M;
    }
    cout<<ans<<endl;
    return 0;
}


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

int a, b, c, x, ans;

int main() {
  cin >> a >> b >> c >> x;
  ans = 0;
  for (int i = 0; i <= a ;i++) {
    for (int j = 0; j <= b; j++){
      for (int k = 0; k <= c;k++){
        if (x == 500 * i + 100 * j + 50 * k) ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
N=int(input())
b=list(map(int,input().split()))

b.reverse()
ans=[]
disable=False

for i in range(N):
    for j in range(len(b)):
        if b[j]==len(b)-j:
            ans.append(b.pop(j))
            break
        if j==len(b)-1:
            disable=True
            ans=[-1]
            break
    if disable:
        break

ans.reverse()
for a in ans:
    print(a)

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

typedef long long int ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define ar array
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll mod = 1e9 + 7;
const ll inf = 2e9 + 5;
double PI = 3.14159265358979323846;

void solve() {

    string s;
    cin >> s;
    int sum = 0;
    for(int i = 0;i < s.length();i++){
        sum = (sum + s[i]-'0')%9;
    }
    if(sum == 0){
        cout << "Yes" << endl;
    }else{
        cout <<  "No" << endl;
    }
}

int32_t main()
{
    IOS
    // int T; cin >> T; while (T--)
    solve();
    return 0;
}


Measured memory_bytes: 3716
n,m=map(int,input().split(" "))
h=list(map(int,input().split(" ")))
g=[1]*n
for i in range(m):
  r=list(map(int,input().split(" ")))
  if h[r[0]-1]<=h[r[1]-1]:
    g[r[0]-1]*=0
  if h[r[0]-1]>=h[r[1]-1]:
    g[r[1]-1]*=0
    
print(sum(g))

Measured memory_bytes: 80272
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))

n,m= m()

print(n-m)


Measured memory_bytes: 6340
'use strict'

function main(inp) {
  inp = inp.trim().split('\n')
  const N = Number(inp.shift())
  inp = inp[0].split(' ').map(n => Number(n));

  let ans = 'APPROVED';
  for (let n of inp) {
    if (n % 2 === 0) {
      if ((n % 3 !== 0) && (n % 5 !== 0)) {
        ans = 'DENIED';
      }
    }
  }
  console.log(ans)
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));


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

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
// #define int long long
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;

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

ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }
ll LCM(ll a, ll b) { return a / GCD(a, b)* b; }

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

inline bool inside(int y, int x, int H, int W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

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

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n; cin>>n;
  vll x(n);
  rep(i,n) cin>>x[i];
  vll d(n-1);
  rep(i,n-1) d[i]=x[i+1]-x[i];
  
  ll c=0, ans=0;
  rep(i,n-1){
    c=(c+modinv(i+1,MOD))%MOD;
    ans=(ans+c*d[i])%MOD;
  }
  ll fact=1;
  reps(i,n-1) fact=fact*i%MOD;
  ans=ans*fact%MOD;
  
  cout<<ans<<endl;
}

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

using namespace std;

# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define REPG(i, h, x) for(int i = h[x]; ~i; i = edge[i].next)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)

const int N = 15 + 3, N_ = 15, M = 15 * 14 / 2 + 5, MOD = 1e9 + 7;
typedef long long ll;
//f[i][S] 
// g[i][S]

bool e[N][N];
int n, m, S;
int g[N][(1 << N_) - 1 + 5], f[N][(1 << N_) - 1 + 5];
int dp[(1 << N_) - 1 + 5], id[(1 << N_) - 1 + 5], pw[M];

inline void inc(int &a, int b) { a = (a + b) % MOD; }

void pre() {
	REP(i, 1, n) {
		REP(j, 0, S) {
			f[i][j] = f[i][j - (j&-j)] + e[i][id[j&-j]];
		}
	}
	REP(i, 1, n) {
		REP(j, 0, S) {
			int p = j & -j;
			if(e[i][id[p]]) inc(g[i][j], (g[i][j - p] * 2 + 1) % MOD);
			else g[i][j] = g[i][j - p] % MOD;
		}
	}
}
int main() {
	scanf("%d%d", &n, &m);
	S = (1 << n) - 1;
	pw[0] = 1;
	REP(i, 1, n) id[(1 << i - 1)] = i;
	REP(i, 1, m) pw[i] = 1ll * pw[i - 1] * 2 % MOD; //1ll
	REP(i, 1, m) {
		int x, y; scanf("%d%d", &x, &y);
		e[x][y] = 1;
	}
    pre();
    dp[0] = 1;
	REP(s, 1, S) {
		for(int t = (s - 1) & s; ; -- t, t &= s) { // origin
//			if(((t & 1) ^ (t & 2)) == 0) {
			 if (((((s^t)&1)&&(t&2)) == 0) && ((((s^t)&2)&&(t&1)) == 0)) {
				int tmp = 1, tmp2 = 0;
				for(int j = t; j; j -= j & -j) tmp = 1ll * tmp * g[id[j & -j]][t ^ s] % MOD;
				for(int j = t ^ s; j; j -= j & -j) inc(tmp2, f[id[j & -j]][t]);
				inc(dp[s], 1ll * (1ll * (1ll * pw[tmp2] % MOD) * tmp % MOD) * dp[t] % MOD);
			}
			if(!t) break;
		}
	}
    printf("%d\n", (((pw[m] - dp[S]) % MOD) + MOD) % MOD);
	return 0;
}
/*5 10
2 4
3 4
2 5
2 3
1 2
3 5
1 3
1 5
4 5
1 4

*/

Measured memory_bytes: 4608
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
//#include"functions.h"
#define pb push_back
#define pf push_front
#define ppb pop_back
#define mp make_pair
#define np next_permutation
#define fi first
#define sc second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pff pair<float,float>
#define pdd pair<double,double>
#define psi pair<string,int>
#define pis pair<int,string>
#define ppi pair<pii,int>
#define pdi pair<pii,pii>
#define INF 0x7fffffff
#define LLINF 0x7fffffffffffffff
#define EPS 1e-5
#define LDEPS 1e-9
#define MOD 1000000007
#define E 2.7182818284
#define PI 3.1415926535
#define FOR(a,b) for(int a=0;a<b;a++)
#define FORN(a,m,n) for(int a=m;a<n;a++)
#define REP(a,m,n) for(int a=0;a<m;a+=n)
#define REPN(a,m,n,p) for(int a=m;a<n;a+=p)
#define frestream freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define stdfopen(a,b) freopen(a,"r",stdin);freopen(b,"w",stdout);
#define ifopen(a) freopen(a,"r",stdin);
#define ofopen(a) freopen(a,"w",stdout);
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define MOD 1000000007
typedef long long ll;
typedef long double ld;
using namespace std;

int main(){
	int a,b,c;
	cin>>a>>b>>c;
	c-=(a-b);
	cout<<max(c,0)<<endl;
	return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A = [input() for _ in range(N)]
B = [input() for _ in range(M)]
for i in range(N - M + 1):
    for j in range(N - M + 1):
        for x in range(M):
            if A[j + x][i:i + M] != B[x]:
                break
        else:
            print("Yes")
            exit()
print("No")


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  int h,w,k;
  cin>>h>>w>>k;
  char c[h][w];
  rep(i,0,h){
    rep(j,0,w){
      cin>>c[i][j];
    }
  }
  int ans=0;
  rep(i,0,1<<(h+w)){
    char d[h][w];
    rep(j,0,h){
      rep(l,0,w){
        d[j][l]=c[j][l];
      }
    }
    rep(j,0,h){
      if(i>>j & 1){
        rep(l,0,w){
          d[j][l]='x';
        }
      }
    }
    rep(j,0,w){
      if(i>>(h+j) & 1){
        rep(l,0,h){
          d[l][j]='x';
        }
      }
    }
    int cnt=0;
    rep(j,0,h){
      rep(l,0,w){
        if(d[j][l]=='#') cnt++;
      }
    }
    if(cnt==k) ans++;
  }
  cout<<ans<<endl;
}

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

const long long MOD = (long long) 1e9 + 7;

template<typename T>
T modpow(T b, T p) {
  if (p == 0) {
    return 1;
  }
  T ans = modpow(b * b % MOD, p / 2);
  if (p % 2 == 1) {
    ans = (ans * b) % MOD;
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int x, y;
  cin >> x >> y;
  int a, b = -1;
  for (a = 0; a <= (int) 1e6; a++) {
    if (x - a == 2 * (y - 2 * a) && (x - a) / 2 >= 0) {
      b = (x - a) / 2;
      break;
    }
  }
  if (b == -1) {
    cout << 0 << '\n';
    return 0;
  }
  long long ans = 1;
  for (long long i = 1; i <= a + b; i++) {
    ans = (ans * i) % MOD;
  }
  for (long long i = 1; i <= a; i++) {
    ans = (ans * modpow(i, MOD - 2)) % MOD;
  }
  for (long long i = 1; i <= b; i++) {
    ans = (ans * modpow(i, MOD - 2)) % MOD;
  }
  cout << ans << '\n';
  return 0;
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;

const int INF = 1000000000;
const int MOD = 1000000007;

int main () {
    int n; cin >> n;
    int t = 0, x = 0, y = 0;
    bool flg = true;

    rep(i, n) {
        int nt, nx, ny;
        cin >> nt >> nx >> ny;
        int d = abs(nx - x) + abs(ny - y), dt = nt - t;
        if (d > dt || (dt - d) % 2) flg = false;
        t = nt, x = nx, y = ny;
    }
    cout << (flg ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  string s;
  cin>>s;
  if(n%2) 
  {
    cout<<"No";
    return 0;
  }
  if(s.substr(0, n/2) == s.substr(n/2)) cout<<"Yes";
  else cout<<"No";
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>
#include <set>
using namespace std;

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


int main() {
	string S, T;
	cin >> S >> T;

	for (int i=0; i<S.size(); i++) {
		string test = "";
		rep(j, S.size()) {
			int idx = (j + i)%S.size();
			test += S[idx];
		}
		if (test == T) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		long k = Long.parseLong(sc.next());
		int[] a = new int[n];
		long[] d = new long[100001];
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(sc.next());
			d[a[i]] += Integer.parseInt(sc.next());
		}
		Arrays.sort(a);
		int[] b = new int[n];
		int in = 0;
		for (int i = 0; i < n;) {
			int index = i;
			while (i < n && a[i] == a[index])
				i++;
			b[in++] = a[index];
		}
		long count = 0;
		for (int i = 0; i < n; i++) {
			count += d[b[i]];
			if (count >= k) {
				System.out.println(b[i]);
				break;
			}
		}
	}
}

Measured memory_bytes: 50744
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#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 rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int x, y, z, k;
    cin >> x >> y >> z >> k;
    vector<ll> a(x), b(y), c(z);
    rep(i, x) cin >> a[i];
    rep(i, y) cin >> b[i];
    rep(i, z) cin >> c[i];
    vector<ll> ab, abc;
    
    rep(i, x) {
        rep(ii, y) {
            ab.emplace_back(a[i] + b[ii]);
        }
    }
    
    sort(all(ab), greater<ll>());
    
    rep(i, min(k, sz(ab))) {
        rep(ii, z) {
            abc.emplace_back(ab[i] + c[ii]);
        }
    }
    
    sort(all(abc), greater<ll>());
    
    rep(i, k) {
        cout << abc[i] << endl;
    }
    
    return 0;
}

Measured memory_bytes: 42856
#include "bits/stdc++.h"
#include<assert.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
const int inf = 1e17;
const int mod = 1000000007;
typedef pair<int, int> P;
typedef pair<int, P> PP;

int sgn(int a) {
	if (a < 0)return -1;
	if (a > 0)return 1; return 0;
}

signed main() {
	int t1, t2, a1, a2, b1, b2;
	cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;
	a1 -= b1;
	a2 -= b2;
	if (t1*a1 + t2*a2 ==0) {
		cout << "infinity" << endl;
	}
	else {
		int ans = 0;
		if (a1<0) {
			a1 *= -1;
			a2 *= -1;
		}
		if (a1*t1+a2*t2>0)cout << 0 << endl;
		else {
			int d1 = t1*abs(a1), d2 = t2*abs(a2);
			int S = abs(d1-d2);
			int cnt = (d1+S-1) / S*2;
			cnt--;
			if (d1%S == 0)cnt++;
			cout << cnt << endl;

		}
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <random>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main() {
    int n; cin >> n;
    int a[n+1]; int b[n];
    rep(i,n+1) cin >> a[i];
    rep(i, n) cin >> b[i];
    ll ans = 0;
    rep (i, n) {
        // i番目の街のモンスターを倒せるだけ倒す
        int kill = min(a[i], b[i]);
        ans += (ll) kill;
        // i番目の勇者が倒せるモンスターの数を減らす
        b[i] -= kill;
        // 余力でi+1番目の街のモンスターを倒せるだけ倒す
        int kill2 = min(a[i+1], b[i]);
        ans += (ll) kill2;
        a[i+1] -= kill2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int MOD = 1000000007;
//const int MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const double pi = acos(-1.0);
const double EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

int main(){
    int N;
    cin >> N;
    ll ans = 0;
    rep2(i, 1, N-1){
        ans += (N-1)/i;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3628
int main()
{
    int a[101][101], b[101][101];
    long long c[101][101], s;
    int i, j, k;
    int n, m, l;
 
    scanf("%d%d%d", &n, &m, &l);
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) scanf("%d", &a[i][j]);
    }
    for (i = 0; i < m; i++) {
        for (j = 0; j < l; j++) scanf("%d", &b[i][j]);
    }
 
    for (i = 0; i < n; i++) {
        for (j = 0; j < l; j++) {
            s = 0;
            for (k = 0; k < m; k++) {
                s += a[i][k] * b[k][j];
            }
            c[i][j] = s;
        }
    }
 
    for (i = 0; i < n; i++) {
        printf("%lld", c[i][0]);
        for (j = 1; j < l; j++) printf(" %lld", c[i][j]);
        putchar('\n');
    }
    return 0;
}


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


def inpl():
    return list(map(int, input().split()))


def main():
    max_p = 10**6
    dp_all = [1000] * (max_p + 1)
    dp_odd = dp_all.copy()
    dp_all[0] = 0
    dp_odd[0] = 0

    pollocks = [i * (i + 1) * (i + 2) // 6 for i in range(1, 181)]

    for i in range(max_p):
        for p in pollocks:
            if i + p > max_p:
                break
            if dp_all[i + p] > dp_all[i] + 1:
                dp_all[i + p] = dp_all[i] + 1
            if p % 2 and dp_odd[i + p] > dp_odd[i] + 1:
                dp_odd[i + p] = dp_odd[i] + 1

    while True:
        p = int(input())
        if p == 0:
            break
        print(dp_all[p], dp_odd[p])


main()



Measured memory_bytes: 21152
#-*-coding:utf-8-*-

def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    ans = 1
    flag = 0
    for i in range(1, n):
        if a_list[i] - a_list[i-1] > 0 and flag == 0:
            flag = 1
        elif a_list[i] - a_list[i-1] < 0 and flag == 0:
            flag = 2
        if a_list[i] - a_list[i-1] > 0 and flag == 2:
            ans += 1
            flag = 0
        elif a_list[i] - a_list[i-1] < 0 and flag == 1:
            ans += 1
            flag = 0
    print(ans)
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 14436
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
using namespace std;

typedef long long ll;

int n;
ll k;
ll w[100005], d[100005];

ll cnt(ll x) {
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		if (w[i] > x) continue;
		ans += 1 + (x - w[i]) / d[i];
	}
	return ans;
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; ++i) cin >> w[i] >> d[i];
	deque<pair<ll, ll>> st;
	st.push_back(pair<ll, ll>{ 0LL, (ll)2e18 });
	while (!st.empty()) {
		ll left = st.back().first, right = st.back().second;
		if (right - left <= 1) {
			if (cnt(left) == k) cout << left << endl;
			else cout << right << endl;
			return 0;
		}
		st.pop_back();
		ll mid = left + (right - left) / 2;
		ll c = cnt(mid);
		if (c < k) {
			st.push_back({ mid, right });
		}
		else {
			st.push_back({ left, mid });
		}
	}
	return 0;
}

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

using namespace std;

using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

int main() {
    ll n, m, i, j, k;
    cin >> n;
    vector<ll> A(n);
    for(i=0;i<n;i++){
        cin >> A[i];
    }
    ll ret = 3;
    ll col[3]={};
    col[0]++;
    for(i=1;i<n;i++){
        ll cnt = 0;
        if(A[i]==col[0])cnt++;
        if(A[i]==col[1])cnt++;
        if(A[i]==col[2])cnt++;
        ret*=cnt;
        ret%=MOD;
        if(A[i] == col[0]) col[0]++;
        else if(A[i] == col[1]) col[1]++;
        else if(A[i] == col[2]) col[2]++;
    }
    if(A[0]!=0)cout << 0 << endl;
    else cout << ret << endl;
    return 0;
}

Measured memory_bytes: 1024
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		Scanner sc=new Scanner(System.in);
	    String c=sc.nextLine();
	    switch(c) {
	    case "a":
	    	System.out.println("vowel");
	    	break;
	    case "e":
	    	System.out.println("vowel");
            break;
	    case "i":
	    	System.out.println("vowel");
	    	break;
	    case "o":
	    	System.out.println("vowel");
	    	break;
	    case "u":
	    	System.out.println("vowel");
	    	break;
	    default:
	    	System.out.println("consonant");
	    }

	}

}


Measured memory_bytes: 23764
S = input()
N = len(S)

def isPalindrome(S, i, j):
    i = int(i)
    j = int(j)
    while S[i] == S[j]:
        i+=1
        j-=1
        if i >= j:
            return True
    return False

if isPalindrome(S, 0, N-1) and isPalindrome(S, 0, (N-1)/2-1) and isPalindrome(S, (N+3)/2-1, N-1):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
from itertools import combinations_with_replacement

def main():
  N, M, Q = map(int, input().split())
  abcd = [list(map(int, input().split())) for x in range(Q)]
  ans = 0
  for x in combinations_with_replacement(range(1, M+1), N):
    r = 0
    for a,b,c,d in abcd:
      if x[b-1] - x[a-1] == c:
        r += d
    ans = max(ans,r)
  print(ans)

if __name__ == '__main__':
    main()

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

int main() {
  int x;
  int a;
  int b;
  int c;
  
  cin >> x;
  
  a = x / 100;
  x = x - a * 100;
  
  b = x / 10;
  x = x - b * 10;
  
  c = x / 1;
  
  cout << a + b + c << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
  int n;
  cin>>n;
  ll vec[n][3];
  ll minabs[n];
  for(int i=0;i<n;i++){
    cin>>vec[i][0]>>vec[i][1]>>vec[i][2];
    minabs[i]=min(abs(vec[i][0]),abs(vec[i][1]));
  }
  ll ans[n+1];
  for(int i=0;i<=n;i++){
    ans[i]=1e13;
  }
  int vecb[n];
  int vecc[n];
  ll cost[n];
  ll sum;
  int x=100;
  for(int bit=0;bit<(1<<n);bit++){
    int t=0;
    for(int i=0;i<n;i++){
      if(bit&(1<<i)){
        vecb[i]=1;
        vecc[t]=i;
        t++;
      }
      else{
        vecb[i]=0;
      }
    }
    if(t==n){
      ans[t]=0;
      continue;
    }
    if(t>=x){
      continue;
    }
    for(int i=0;i<n;i++){
      cost[i]=minabs[i];
    }
    for(int bitb=0;bitb<(1<<t);bitb++){
      for(int i=0;i<t;i++){
        if(bitb&(1<<i)){ //縦に引く
          for(int j=0;j<n;j++){
            cost[j]=min(cost[j],abs(vec[j][0]-vec[vecc[i]][0]));
          }
        }
        else{ //横に引く
          for(int j=0;j<n;j++){
            cost[j]=min(cost[j],abs(vec[j][1]-vec[vecc[i]][1]));
          }
        }
      }
      sum=0;
      for(int i=0;i<n;i++){
        sum+=cost[i]*vec[i][2];
        cost[i]=minabs[i];
      }
      ans[t]=min(ans[t],sum);
      if(ans[t]==0){
        x=min(x,t);
      }
    }
  }
  
  for(int i=0;i<n+1;i++){
    if(i>=x){
      cout<<0<<endl;
    }
    else{
      cout<<ans[i]<<endl;
    }
  }
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define FOR(i, k, n) for(int i = (k); i < (n); i++)
#define FORe(i, k, n) for(int i = (k); i <= (n); i++)
#define FORr(i, k, n) for(int i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(int i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;
using ll = long long;

const int INF = 1001001001;

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

int main(void){
  int n;
  cin >> n;
  vector<int> a(n);
  REP(i, n) cin >> a[i];
  vector<int> l(n+1), r(n+1), m(n);
  l[0] = 0, r[n] = 0;
  REP(i, n) l[i+1] = gcd(l[i], a[i]);
  REPr(i, n) r[i] = gcd(r[i+1], a[i]);
  REP(i, n) m[i] = gcd(l[i], r[i+1]);
  int ans = *max_element(ALL(m));
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include<stdio.h> 
#include<bitset> 
#define ll long long
using namespace std;
ll gcd(ll a, ll b) {
	while (b) {
		ll mod = a % b; a = b; b = mod;
	}
	return a;
}

bool cmp(pair<int, ll> A, pair<int, ll> B) {
	return A.second < B.second;
}
int main() {
	int n,k,qty=0;
	cin >> n>>k;
	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		if (temp >= k) {
			qty++;
		}
	}
	cout << qty;
	//system("pause");
	return 0;
}

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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using llu = long long unsigned int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int K,N;
    Scd2(K,N);

    vi a(N);
    Rep(i,N){
        Scd(a[i]);
    }

    int ans = INF;
    Rep(i,N){
        ans = min( ans, (a[(i-1+N)%N]-a[i]+K*2)%K );
        ans = min( ans, (a[i]-a[(i+1)%N]+K*2)%K);
    }

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

    return 0;
}




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

const int INF = 0x3f3f3f3f;
const double EPS = 1e-9; 
const int MAXN = 100000 + 10;


int N, K;
int vis[10];

void solve() {
    scanf("%d%d", &N, &K);
    memset(vis, 0, sizeof vis);
    int temp;
    for (int i = 0; i < K; ++i) {
        scanf("%d", &temp);
        vis[temp] = 1;
    }
    bool flag;
    for (int i = N; i <= 10 * N; ++i ) {
        temp = i;
        flag = 1;
        while(temp) {
            if (vis[temp%10]) {
                flag = 0;
                break;
            }
            temp /= 10;
        }
        if (flag) {
            printf("%d\n", i);
            break;
        }
    } 
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main(){
    string s, t;
    cin >> s >> t;
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    reverse(t.begin(), t.end());
    if ( s < t ) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}


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

int main() {
	int a,b,c;
	int tab[5];
	for (int i=1;i<=3;i++)
	 cin>>tab[i];
	sort(tab+1,tab+4);
	int ans=tab[1]+tab[2];
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 256