akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define MOD 1000000007
#define MOD2 998244353
#define int long long
#define EPS 1e-9
//#define PI 3.14159265358979

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

using namespace std;

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

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

struct edge {
	int from, to, d, c;
	edge(int _from = 0, int _to = 0, int _d = 0, int _c = 0) {
		from = _from;
		to = _to;
		d = _d;
		c = _c;
	}
	bool operator<(const edge &rhs) const {
		return (d == rhs.d) ? (c < rhs.c) : (d < rhs.d);
	}
};
struct aabb {
	int x1, y1, x2, y2;
	aabb(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};

typedef vector< edge > edges;
typedef vector< edges > graph;
struct flow {
	int to, cap, rev, cost;
	flow(int to = 0, int cap = 0, int rev = 0, int cost = 0) : to(to), cap(cap), rev(rev), cost(cost) {}
};
typedef vector< vector< flow > > flows;

const int di[4] = {0, -1, 0, 1};
const int dj[4] = {-1, 0, 1, 0};
const int ci[5] = {0, 0, -1, 0, 1};
const int cj[5] = {0, -1, 0, 1, 0};
const ll LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const double PI = acos(-1);

int pow2(int n) { return 1LL << n; }
template < typename T, typename U >
bool chmin(T &x, const U &y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}
template < typename T, typename U >
bool chmax(T &x, const U &y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

struct initializer {
	initializer() {
		cout << fixed << setprecision(20);
	}
};
initializer _____;

int N, M, K, T, Q, H, W;
signed main() {
	cin >> K >> Q;
	vector< int > D(K);
	rep(i, K) cin >> D[i];
	while (Q--) {
		int X;
		cin >> N >> X >> M;
		int ans = N - 1;
		vector< int > B(K);
		rep(i, K) B[i] = D[i] % M;
		rep(i, K) if (B[i] == 0) {
			ans -= (N - 1 - i + K - 1) / K;
		}
		int anm1 = X;
		rep(i, K) {
			anm1 += B[i] * ((N - 1 - i + K - 1) / K);
		}
		int a0 = X;
		ans -= (anm1 / M - a0 / M);
		cout << ans << endl;
	}
	return 0;
}

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

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc =new Scanner(System.in);
		int w = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int gap = 0;
		if(a+w < b) {
			gap = b - (a + w);
		}else if(a > b + w) {
			gap = a - (b + w);
		}
		System.out.println(gap);
	}

}

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

int main() {
	int S;
    cin >> S;
    int H , J , I ;
    H = S / 100;
    S = S % 100;
    J = S / 10;
    S = S % 10;
    I = S;
    cout << H + J + I << endl;
}


Measured memory_bytes: 3548
import java.util.*;

public class Main
{
    static long dp[][];
    static long min(int i , int j , int arr[])
    {
        if(i==j)
        return 0;
        
        if(dp[i][j] != -1)
        return dp[i][j];
        
        long sum = 0;
        for(int k = i ;  k <= j ; k++)
        {
            sum += arr[k];
        }
        dp[i][j] = Long.MAX_VALUE;
        for(int k = i ; k < j ; k++)
        {
            dp[i][j] = Math.min(dp[i][j] , min(i,k,arr)+min(k+1,j,arr)+sum);
        }
        return dp[i][j];
    }
    public static void main(String []args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int arr[] = new int[n];
        for(int i = 0 ; i < n ; i++)
        {
            arr[i] = sc.nextInt();
        }
        
        dp = new long[n][n];
        for(int i = 0 ; i < n ; i++)
        {
            for(int j = 0 ; j < n ; j++)
            {
                dp[i][j] = -1;
            }
        }
        System.out.println(min(0,n-1,arr));
    }
}

Measured memory_bytes: 40800
n, m = map(int, input().split())
n -= 1
x = [[] for _ in range(200000)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    x[a].append(b)

cnt = 0
for i in x[0]:
    if n in x[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Measured memory_bytes: 33508
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

int main() {
  int n; cin >> n;
  vector<int> a(n); REP(i, n) cin >> a[i];
  if (n % 2 == 0) {
    vector dp(n, vector(2, -LINF));
    dp[1][0] = a[0];
    dp[1][1] = a[1];
    for (int i = 3; i < n; i += 2) {
      dp[i][0] = dp[i - 2][0] + a[i - 1];
      dp[i][1] = max(dp[i - 2][0], dp[i - 2][1]) + a[i];
    }
    cout << max(dp[n - 1][0], dp[n - 1][1]) << '\n';
  } else {
    vector dp_l(n, vector(2, -LINF));
    dp_l[1][0] = a[0];
    dp_l[1][1] = a[1];
    for (int i = 3; i < n; i += 2) {
      dp_l[i][0] = dp_l[i - 2][0] + a[i - 1];
      dp_l[i][1] = max(dp_l[i - 2][0], dp_l[i - 2][1]) + a[i];
    }
    vector dp_r(n, vector(2, -LINF));
    dp_r[n - 2][0] = a[n - 2];
    dp_r[n - 2][1] = a[n - 1];
    for (int i = n - 4; i >= 0; i -= 2) {
      dp_r[i][0] = max(dp_r[i + 2][0], dp_r[i + 2][1]) + a[i];
      dp_r[i][1] = dp_r[i + 2][1] + a[i + 1];
    }
    ll ans = -LINF;
    REP(i, n) {
      if (i & 1) {
        // chmax(ans, dp_l[i][0] + (i + 2 < n ? max(dp_r[i + 2][0], dp_r[i + 2][1]) : 0LL));
        // chmax(ans, dp_r[i][1] + (i >= 2 ? max(dp_l[i - 2][0], dp_l[i - 2][1]) : 0LL));
      } else {
        chmax(ans, (i > 0 ? max(dp_l[i - 1][0], dp_l[i - 1][1]) : 0LL) + (i + 1 < n ? max(dp_r[i + 1][0], dp_r[i + 1][1]) : 0LL));
      }
    }
    cout << ans << '\n';
  }
  return 0;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> a(n+1), b(n+1);
    rep(i,n) cin >> a[i+1]; //1から
    for(int i = n; i >= 1; --i) {
        int sum = 0;
        for(int j = i+i; j <= n; j+=i) {
            sum ^= b[j];
        }
        b[i] = sum^a[i];
    }
    vector<int> ans;
    for(int i = 0; i <= n; ++i) {
        if(b[i]) ans.push_back(i);
    }
    cout << ans.size() << endl;
    rep(i,ans.size()){
        printf("%d ", ans[i]);
    }
    return 0;
}

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

int main() {
  
  int A,B;
  cin >> A >>B;
  
  int count=0,sum=0;
  
  while(count < 2){
    if(A>=B){ sum+=A;
             A--;
           }else{
     		 sum+=B;
      		B--;
    }
    count++;
  }
  cout << sum <<endl;
  return 0;
}


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

typedef long long ll;
typedef long double ld;
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
    int N, M, X, Y; cin >> N >> M >> X >> Y;
    vector<int> x(N), y(M);
    int xM = -inf, ym = inf;
    for (int i = 0; i < N; i++) {
        cin >> x.at(i);
        xM = max(xM, x.at(i));
    }
    for (int i = 0; i < M; i++) {
        cin >> y.at(i);
        ym = min(ym, y.at(i));
    }
    string ans = "War";
    for (int Z = X + 1; Z <= Y; Z++) {
        if (Z > xM && Z <= ym) {
            ans = "No War";
            break;
        }
    }
    cout << ans << endl;
}

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

int main() {
  char X, Y;
  cin >> X >> Y;
  
  if (X < Y) {
    cout << '<' << endl;
  } else if (X > Y) {
    cout << '>' << endl;
  } else {
    cout << '=' << endl;
  }
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

int main(){
  ll n;
  cin >> n;
  ll ans = 1;
  for(int i = 1; i <= n; ++i){
    ans *= i;
    ans %= mod;
  }
  cout << ans << endl;
}

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

struct P {
    int count;
    int index;

    bool operator<(const P &another) const {
            return count < another.count;
    };
};

int main() {
	int N;
	cin >> N;
	vector<P> A(N);
	rep(i,N){
		cin >> A[i].count;
		A[i].index = i;
	}
	sort(all(A));
	rep(i,N){
		printf("%d ",A[i].index + 1);
	}
}

Measured memory_bytes: 1536
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        sc.close();

        if (Math.abs(c - a) <= d || ((Math.abs(b - a) <= d) && Math.abs(c - b) <= d)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 20944
s = input()
n = len(s)

cnt_1 = 0
cnt_2 = 0

#左端のタイルの色が黒
for i in range(n):
  if i % 2 != int(s[i]):
    cnt_1 += 1

#左端のタイルの色が白    
for i in range(n):
  if i % 2 == int(s[i]):
    cnt_2 += 1
      
print(min(cnt_1, cnt_2))

Measured memory_bytes: 3188
/**
 *    Author:  "Robin Singh" !!!!    
**/
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ef emplace_front
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define str string 
#define szz(v) ((int)(v).size())  
#define vi vector<int>
#define vll vector<ll>
#define fr(i, j, k) for(i = j; i < k; i++)
#define bk(i, j, k) for(i = j; i >= k; i--)
#define frit(it, a) for(__typeof((a).begin()) it = a.begin(); it != a.end(); ++it)
#define mem(ptr)  memset(ptr, 0, sizeof ptr)  // use fill() for value other than 0 //
#define rtn return 
#define time fprintf(stderr, "\nTIME = %lf\n", 1.0 * clock()/CLOCKS_PER_SEC)
#define nl "\n"
#define INF 1LL<<61
#define inf 1<<30
#define dbg(x) (cerr << #x << ": " << x << "\n")
const long long mod = 1e9+7;

ll gcd(ll a,ll b) { return b==0 ? a : gcd(b, a%b); }
ll expo(ll x, ll y){ ll res = 1; x = x % mod;  while (y > 0) { if (y & 1)res = (res*x) % mod; y = y>>1;x = (x*x) % mod;}return res;}
void matmul(ll a[][2], ll b[][2]) { ll tmp[2][2]; for(int i=0; i<2; i++) { for(int j=0; j<2; j++) { tmp[i][j] = 0; for(int k=0; k<2; k++) tmp[i][j] = (tmp[i][j] + a[i][k]*b[k][j]) % mod; }} for(int i=0; i<2; i++) for(int j=0; j<2; j++) a[i][j] = tmp[i][j]; }
ll fibo(int n)    // returns nth fibonacci number, also S(n) = f(n+2)-1
{ if(n == 0) return 0; else if(n == 1) return 1; ll T[2][2] = { {0, 1} , {1, 1} }; ll res[2][2] = { {1, 0}, {0,1} }; n--; while(n) { if(n & 1) matmul(res, T); n >>= 1; matmul(T, T); } return res[1][1]; }

int cnt[3][31];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, c;
    cin >> n >> c;
    int d[c+1][c+1];
    for(int i=1; i<=c; i++)
        for(int j=1; j<=c; j++)
            cin >> d[i][j];
    int col[n+1][n+1];
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> col[i][j];
            cnt[(i+j)%3][col[i][j]]++;
    
        }
    }
    
    int ans = inf, tmp = 0;
    for(int i=1; i<=c; i++){
        for(int j=1; j<=c; j++){
            if(i==j) continue;
            for(int k=1; k<=c; k++){
                if(j==k || i==k) continue;
                int tmp = 0;
                for(int z=1; z<=c; z++)
                    tmp += d[z][i]*cnt[0][z];
                for(int z=1; z<=c; z++)
                    tmp += d[z][j]*cnt[1][z];
                for(int z=1; z<=c; z++)
                    tmp += d[z][k]*cnt[2][z];
                ans = min(ans, tmp);
            }
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 1280
#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
#define ll long long int
//#define INT_MIN -2147483648
using namespace std;
void swap(int* x,int* y)
{
  int temp = *x;
  *x=*y;
  *y=temp;
}
int main()
{
  int n;
  cin>>n;
  vector<int>data(3*n,0);

  for(int i=0;i<n*3;i++)
  {
    cin>>data[i];
  }

  vector<int> minheap(n+1,0);
  vector<int> maxheap(n+1,0);
  ll sum1=0,sum2=0;
  for(int i=0;i<n;i++)
  {
    minheap[i]=data[i];
    sum1+=minheap[i];
    for(int j=i;j>0;j=(j-1)/2)
    {
      if(minheap[(j-1)/2]<=minheap[j])break;
      swap(&minheap[(j-1)/2],&minheap[j]);
    }
  }
  for(int i=0;i<n;i++)
  {
    maxheap[i]=data[(2*n)+i];
    sum2+=maxheap[i];
    for(int j=i;j>0;j=(j-1)/2)
    {
      if(maxheap[(j-1)/2]>=maxheap[j])break;
      swap(&maxheap[(j-1)/2],&maxheap[j]);
    }
  }
  vector<ll> psum(n+1,0);
  vector<ll> ppar(n+1,0);
  vector<ll> nsum(n+1,0);
  vector<ll> npar(n+1,0);
  psum[0]=sum1;nsum[n]=sum2;



  for(int i=0;i<n;i++)
  {
    minheap[n]=data[n+i];
    for(int j=n;j>0;j=(j-1)/2)
    {
      if(minheap[j]>=minheap[(j-1)/2])break;
      swap(&minheap[j],&minheap[(j-1)/2]);
    }
    psum[i+1]=psum[i]+data[n+i];
    ppar[i+1]=ppar[i]+minheap[0];
    minheap[0]=minheap[n];
    for(int j=0;j<n;)
    {
      int smallest=j;
      int left=(2*j)+1;
      int right=(2*j)+2;
      if(left<n&&minheap[left]<minheap[j])smallest=left;
      if(right<n&&minheap[right]<minheap[smallest])smallest=right;
      if(smallest==j)break;
      swap(&minheap[j],&minheap[smallest]);
      j=smallest;
    }
  }
  for(int i=0;i<n;i++)
  {
    maxheap[n]=data[2*n-1-i];
    for(int j=n;j>0;j=(j-1)/2)
    {
      if(maxheap[j]<=maxheap[(j-1)/2])break;
      swap(&maxheap[j],&maxheap[(j-1)/2]);
    }
    nsum[n-1-i]=nsum[n-i]+data[2*n-1-i];
    npar[n-1-i]=npar[n-i]+maxheap[0];
    maxheap[0]=maxheap[n];
    for(int j=0;j<n;)
    {
      int largest=j;
      int left=(2*j)+1;
      int right=(2*j)+2;
      if(left<n&&maxheap[left]>maxheap[j])largest=left;
      if(right<n&&maxheap[right]>maxheap[largest])largest=right;
      if(largest==j)break;
      swap(&maxheap[j],&maxheap[largest]);
      j=largest;
    }
  }
  ll max=LLONG_MIN;
  for(int i=0;i<=n;i++)
  {
    //cout<<psum[i]<<" "<<ppar[i]<<" "<<nsum[i]<<" "<<npar[i]<<"\n";
    ll val=(psum[i]-ppar[i])-(nsum[i]-npar[i]);
    if(max<val)max=val;
  }
  cout<<max;
  return 0;
}


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

const long long INF = 1000000000;

typedef long long ll;

#define writeln(n) cout<<n<<"\n";

typedef pair<int, int> P;
typedef pair<string, int> Psi;


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

	int a,b;cin>>a>>b;
	
	if(b==1){writeln(0);
		return 0;
	}

	b = max(0,b-a);

	if(b){
		--a;
		int tmp =b/a;
		if(b%a)tmp++;

		writeln(tmp+1);

	}else {
		writeln(1);
	}

}




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

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

	    int ans = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == t.charAt(i)){
                ans++;
            }
        }

        System.out.println(ans);

    }
}


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

const double PI = 3.14159265358979323846;
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//typedef pair<ll, ll> P;
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

std::istream &operator>>(std::istream &in, set<int> &o) {
    ll a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

//const ll mod = 1e10;
typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;


int main() {

    int n;
    cin >> n;


    vector<ll> left(n + 1), right(n + 1);
    rep(i, n) cin >> left[i] >> right[i];

    sort(left.rbegin(), left.rend());
    sort(right.begin(), right.end());

    ll ans = 0;
    rep(i, n + 1) {
        if (left[i] > right[i]) {
            ans += 2 * (left[i] - right[i]);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <tuple>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
using ll = long long;

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n), s(n+1, 0);
    map<ll, ll> seq;
    for(int i = 0; i< n; i++){
        cin >> a[i];
        s[i+1] = s[i] + a[i];
        seq[s[i+1]]++;
    }
    seq[0]++;
    auto combination = [&](ll x){
        return x * (x-1) / 2;
    };
    ll ans = 0;
    for(int i = 1; i< n+1; i++){
        if(seq[s[i]] > 1){
            ans += combination(seq[s[i]]);
            seq[s[i]] = 0;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 18764
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,t;
    int a[100];
    for(i=1; i<=5; i++)
    {
        cin>>a[i];
        if(a[i]==0)
        {
            t=i;
        }
    }
    cout<<t;
    return 0;
}




Measured memory_bytes: 3628
if __name__ == "__main__":
    n = int(input())
    coordinates = [complex(*map(int, input().split())) for _ in range(n)]
    vecs = [b - a for a, b in zip(coordinates, coordinates[1:] + [coordinates[0]])]
    prev = vecs[0]

    for i in range(1, n):
        cur = vecs[-i]
        if cur.real * prev.imag - prev.real * cur.imag < -1e-6:
            print(0)
            exit(0)
        prev = cur

    print(1)



Measured memory_bytes: 5632
//FIRST THINK THEN CODE.

#include <bits/stdc++.h>
 
 
using namespace std;
 
typedef long long ll;
 
//#define MOD 998244353
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define rrep(i,a,b) for(ll i=a;i>b;--i)
#define FOR(i,n)  for(ll i=0;i<n;i++)
#define vi vector<int>
#define vl vector<ll>
#define ld long double
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define pii pair<int,int>
#define pll pair<long,long>
#define vpii vector<pii>
#define vpll vector<pll>
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define d1(x) cout<<(x)<<endl
#define d2(x,y) cout<<(x)<<" "<<(y)<<endl
#define d3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define d4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl
#define PI 3.1415926535897932384626433832795
#define fix(f,n) fixed<<setprecision(n)<<f
#define all(x) x.begin(),x.end()
#define rev(p) reverse(p.begin(),p.end());
#define endl "\n"
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define popcount(x) __builtin_popcountll(x)
#define sz(x) ((ll)x.size())
const ll M=1000000007;
const ll MM=998244353;
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";

 
ll newmod(ll a,ll b)
 {
  return ((a%b)+b)%b;
}
 
 
ll powM(ll a,ll b,ll m )
{ 
  if(a<=0)return 0;
  a%=m;
  if(!b)return 1;
  ll ans=1LL;
  while(b)
  {
    if(b&1)ans=ans*a%m;
    a=a*a%m;
    b>>=1;
  }
 
return ans;
}


 
ll poww(ll a,ll b)
{ 
  
  ll ans=1;
  while(b)
  {
    if(b&1)ans=ans*a;
    a=a*a;
    b>>=1;
  }
 
return ans;

}

template<typename T,typename F>
void chmax( T &a,F b){
  if(b>a)a=b;
}

template<typename T,typename F>
void chmin( T &a,F b){
  if(b<a)a=b;
}




const ll N=1e5+5;

ll sp[N];

void sieve(){
  for(int i=1;i<N;i++)sp[i]=i;

    for(int i=2;i<N;i++){
      if(sp[i]==i){
        for(int j=i*i;j<N;j+=i){
          if(sp[j]==j)sp[j]=i;
        }
      }
    }
}

  

int main()
{ 

IOS;

ll x;cin>>x;

ll ans=0;

if(x>=400&&x<600)ans=8;
if(x>=600&&x<800)ans=7;

if(x>=800&&x<1000)ans=6;

if(x>=1000&&x<1200)ans=5;

if(x>=1200&&x<1400)ans=4;

if(x>=1400&&x<1600)ans=3;

if(x>=1600&&x<1800)ans=2;

if(x>=1800&&x<2000)ans=1;

cout<<ans;

//end_routine();

return 0;
 
}


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

typedef double db;
typedef long long ll;
int main(){
	ll n;
	cin>>n;
	ll k=100;
	int cnt=0;
	while(k<n){
		k=ll(k*1.01);
		//cout<<k<<endl;
		cnt++;
	}
	cout<<cnt;

	return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

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

    int r;
    cin >> r;

    cout << 3 * r * r << "\n";

    return 0;
}



Measured memory_bytes: 256
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    if(N % 2 == 1){
        print(0);
        return 0;
    }
    ll num2 = 0;
    ll n = 2;
    while(n <= N){
        num2 += N/n;
        n *= 2;
    }
    ll num5 = 0;
    n = 5;
    while(n <= N){
        ll v1 = (N/n)/2;
        num5 += v1;
        n *= 5;
    }
    ll ans = min(num2, num5);
    print(ans);

    

}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

class DisjointSet{
    public:
        vector<ll> rank,p,siz;

        DisjointSet(){}
        DisjointSet(ll size){
            rank.resize(size,0);
            p.resize(size,0);
            siz.resize(size,1);
            rep(i,size) makeSet(i);
        }

        void makeSet(ll x){
            p[x] = x;
            rank[x] = 0;
        }

        bool same(ll x, ll y){
            return root(x) == root(y);
        }

    
        void unite(ll x, ll y){
            x = root(x);
            y = root(y);
            if(rank[x] > rank[y]){
                siz[x] += siz[y];
                p[y] = x;
            }
            else{
                siz[y] += siz[x];
                p[x] = y;
                if(rank[x] == rank[y]) rank[y]++;
            } 
        }
        ll root(ll x){
            if(x != p[x]){
                p[x] = root(p[x]);
            }
            return p[x];
        }

        ll size(ll x){
            return siz[root(x)];
        }

};


int main(){
	int N,M; cin >> N >> M;
	vector<vector<int>> lang(M);
	rep(i,N){
		int K; cin >> K;
		rep(j,K){
			int L; cin >> L;
			L--;
			lang[L].push_back(i);
		}
	}
	DisjointSet uf(N);
	rep(i,M){
		rep(j,lang[i].size()-1){
			if(!uf.same(lang[i][j],lang[i][j+1])) uf.unite(lang[i][j],lang[i][j+1]);
		}
	}
	cout << (uf.size(0) == N ? "YES" : "NO") << endl;
}

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

if sum([x<0 for x in a])%2 == 0:
    print(sum([x if x > 0 else -x for x in a]))
else:
    print(sum([x if x > 0 else -x for x in a]) - min(list(map(abs, a))) * 2)

Measured memory_bytes: 15020
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int main() {
	string S;
	cin >> S;
	bool can = false;
	for (int i = 0; i < S.size(); ++i) {
		if (S.substr(i, 7) == "keyence") {
			if (i + 7 == S.size() || i == 0) {
				can = true;
			}
		}
	}
	if (S[0] == 'k') {
		for (int j = 1; j <= S.size() - 6; ++j) {
			if (S.substr(j, 6) == "eyence") {
				if (j + 6 == S.size()) {
					can = true;
				}
			}
		}
	}
	if (S.substr(0, 2) == "ke") {
		for (int j = 2; j <= S.size() - 5; ++j) {
			if (S.substr(j, 5) == "yence") {
				if (j + 5 == S.size()) {
					can = true;
				}
			}
		}
	}
	if (S.substr(0, 3) == "key") {
		for (int j = 3; j <= S.size() - 4; ++j) {
			if (S.substr(j, 4) == "ence") {
				if (j + 4 == S.size()) {
					can = true;
				}
			}
		}
	}
	if (S.substr(0, 4) == "keye") {
		for (int j = 4; j <= S.size() - 3; ++j) {
			if (S.substr(j, 3) == "nce") {
				if (j + 3 == S.size()) {
					can = true;
				}
			}
		}
	}
	if (S.substr(0, 5) == "keyen") {
		for (int j = 5; j <= S.size() - 2; ++j) {
			if (S.substr(j, 2) == "ce") {
				if (j + 2 == S.size()) {
					can = true;
				}
			}
		}
	}
	if (S.substr(0, 6) == "keyenc") {
		for (int j = 6; j <= S.size() - 1; ++j) {
			if (S[j] == 'e') {
				if (j + 1 == S.size()) {
					can = true;
				}
			}
		}
	}
	if (can)cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int S,h,m,s;
	
	scanf("%d",&S);
	((S>=0)&&(S<=86400));
	h=S/3600;
	m=S%3600/60;
	s=S%3600%60;
	printf("%d:%d:%d\n",h,m,s);
	return 0;
}

Measured memory_bytes: 592
#include <math.h>
#include <ctype.h>
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define REP(i, n) for(int i = 0; i < n; i++)

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

    int C[n], S[n], F[n];
    REP(i, n - 1) cin >> C[i] >> S[i] >> F[i];

    int t;
    REP(i, n){
        t = 0;
        FOR(j, i, n - 1){
            if(t < S[j]) t = S[j];
            if(t % F[j] != 0) t += F[j] - (t % F[j]);
            t += C[j];
        }
        cout << t << endl;
    }

    return 0;
}

Measured memory_bytes: 256
X, N = map(int, input().split())
P = list(map(int, input().split()))
ans_p = X
ans_m = X
while True:
    if ans_m not in P:
        ans = ans_m
        break
    if ans_p not in P:
        ans = ans_p
        break
    ans_p += 1
    ans_m -= 1
print(ans)

Measured memory_bytes: 9184
from collections import defaultdict
def prepare(n, MOD):
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs
    #nCr = (factorials[n]%MOD * invs[r]%MOD * invs[n-r]%MOD)%MOD
def main():
    MOD = 1000000007

    n,m=map(int, input().split())
    dd={i:0 for i in range(0,n+1)}
    a = [2]*(n)
    a[-1]=1
    for i in range(m):
        s  = int(input())
        dd[s]+=1
    dp=[0]*(n+1)
    dp[0]=1
    if dd[1]==0:
        dp[1]=1
    else:
        dp[2] = 1
        if dd[2]>0:
            print(0)
            exit()
    for i in range(2,n+1):
        dp[i] = dp[i-1] + dp[i-2]
        if dd[i]>0:
            dp[i]=0
    print(dp[n]%MOD)




if __name__ == '__main__':
    main()


Measured memory_bytes: 470504
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	int a1=a+b;
	int a2=a-b;
	int a3=a*b;
	printf("%d\n",max(max(a1,a2),a3));
	return 0;
}

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

const long long INF = 1000000000;

typedef long long ll;

#define writeln(n) cout<<n<<"\n";

typedef pair<int, int> P;
typedef pair<string, int> Psi;


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

	int sum=0;
	for(int i=0; i<3; i++){
		int tmp;cin>>tmp;

		sum +=tmp;
	}

	if(sum <=21){
		writeln("win");
	}else {
		writeln("bust");
	}

}




Measured memory_bytes: 256
n=int(input())
t,a=map(int,input().split())
h=list(map(int,input().split()))
mini=10**9
for i in h:
    mini=min(mini,abs(t-i*0.006-a))
for i in range(n):
    if mini==abs(t-h[i]*0.006-a):
        print(i+1)
        import sys
        sys.exit()


Measured memory_bytes: 3060
cs = [list(map(int,input().split()))for _ in range(3)]
for i in range(2):
    yoko = abs(cs[0][i] - cs[0][i + 1])
    for j in range(1,3):
        if yoko - abs(cs[j][i] - cs[j][i + 1]) != 0:
            print('No')
            exit()

for i in range(2):
    tate = abs(cs[0+i][0] - cs[1+i][0])
    for j in range(1,3):
        if tate - abs(cs[i][j] - cs[i+1][j]) != 0:
            print('No')
            exit()
print('Yes')

Measured memory_bytes: 62016
import bisect

N = int(input())
A = [int(x) for x in input().split()]

B = sorted(A)
cnt = [0] * (N+1)
for k in range(1, N+1):
    cnt[k] = bisect.bisect_left(B, k+1)
for k in range(N):
    cnt[-1-k] -= cnt[-2-k]

ALL = 0
for i in range(1, N+1):
    ALL += cnt[i]*(cnt[i]-1)//2

for k in range(N):
    ans = ALL - cnt[A[k]]*(cnt[A[k]]-1)//2 + (cnt[A[k]]-1)*((cnt[A[k]]-1)-1)//2
    print(ans)

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

const int N=500000,mod=998244353;
int jc[500010],inv[500010],nmi[500010],mmi[500010],n,m,ans;

int quickmi(int a,int b)
{
	int t=1;
	for (; b; b>>=1,a=1ll*a*a%mod)
		if (b&1) t=1ll*t*a%mod;
	return t;
}

int main()
{
	jc[0]=1;
	for (int i=1; i<=N; i++) jc[i]=1ll*jc[i-1]*i%mod;
	inv[N]=quickmi(jc[N],mod-2);
	for (int i=N; i; i--) inv[i-1]=1ll*inv[i]*i%mod;
	scanf("%d%d",&n,&m),nmi[0]=mmi[0]=1;
	for (int i=1; i<=N; i++) nmi[i]=1ll*nmi[i-1]*(n+1)%mod;
	for (int i=1; i<=N; i++) mmi[i]=1ll*mmi[i-1]*(m+1)%mod;
	for (int i=max(m-n,0); i<=m; i++)
		ans=(ans+(((m-i)&1)?(mod-1ll):(1ll))*nmi[i]%mod*inv[i]%mod*mmi[n-m+i]%mod*inv[n-m+i]%mod*inv[m-i])%mod;
	ans=1ll*ans*jc[n]%mod*jc[m]%mod;
	return printf("%d\n",ans),0;
}

Measured memory_bytes: 8064
#include<iostream>
#include<map>
#include<string.h>
#include<queue>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<cstdlib>
#include<math.h>
#include<set>
#include<array>
using namespace std;

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; }



#define rep(n) for(int i=0;i<(n);i++)
typedef pair<int, int> pii;

typedef long long ll;
typedef pair<ll, ll>pll;
const int MOD = 1000000007;
const int INF = 1 << 29;




int main() {
	int n, a[200001];
		ll b[200001];
	cin >> n;
	rep(n) { cin >> a[i]; }
	ll sum = 0;
	rep(n) {
		sum += a[i];
		b[i] = sum;
	}
	ll mi = llabs(b[n-1]-b[0]-b[0]);
	rep(n-2) {
		mi = min(llabs(b[i] - (b[n - 1] - b[i])), mi);

	}
	cout << mi << endl;
	return 0;
}


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

using namespace std;
using ll = long long;

int const AMAX = 1e5 + 11;

ll freq[AMAX], sum;

void update(ll b, ll c)
{
    sum -= b * freq[b];
    sum += freq[b] * c;
    freq[c] += freq[b];
    freq[b] = 0;
}

inline ll query(void) { return sum; }

int main(void)
{
    int n, q, ai, b, c;
    cin >> n;

    sum = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> ai;
        freq[ai]++;
        sum += ai;
    }

    cin >> q;
    while (q--)
    {
        cin >> b >> c;
        update(b, c);
        cout << query() << endl;
    }

    return 0;
}


Measured memory_bytes: 4364
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;
const int mod = 1e9 + 7;
set <pair<ll, int> > hs;
vector < pair<int, ll> > e[maxn];
const long long inf = 1e16;
int vis[maxn], ord[maxn][2];
void dij(ll *dis, int S, int n, int ty)
{
    for(int i = 1; i <= n; i++) dis[i] = inf, vis[i] = 0;
    dis[S] = 0;
    hs.clear();
    for(int i = 1; i <= n; i++) hs.insert(mp(dis[i], i));
    for(int i = 0; i < n; i++)
    {
        int u = (hs.begin())->se; hs.erase(hs.begin());
        vis[u] = 1; ord[i+1][ty] = u;
        for(int j = 0; j < e[u].size(); j++)
        {
            int v = e[u][j].fi;
            if(dis[v] > dis[u] + e[u][j].se)
            {
                hs.erase(mp(dis[v], v));
                dis[v] = dis[u] + e[u][j].se;
                hs.insert(mp(dis[v], v));
            }
        }
    }
}
int n, m, s, t, x, y, c;
ll ds[maxn], dt[maxn];
ll dp[maxn], dp2[maxn];
int main()
{
    cin>>n>>m;
    cin>>s>>t;
    for(int i = 1; i <= m; i++){
        scanf("%d %d %d", &x, &y, &c);
        e[x].push_back(mp(y, c));
        e[y].push_back(mp(x, c));
    }
    dij(ds, s, n, 0);
    dij(dt, t, n, 1);
    dp[s] = 1;
    for(int i = 1; i <= n; i++){
        int x = ord[i][0];
        for(auto y : e[x]) {
            if(ds[x] + y.se + dt[y.fi] != ds[t]) continue;
            (dp[y.fi] += dp[x]) %= mod;
        }
    }
    dp2[t] = 1;
    for(int i = 1; i <= n; i++){
        int x = ord[i][1];
        for(auto y : e[x]) {
            if(dt[x] + y.se + ds[y.fi] != ds[t]) continue;
            (dp2[y.fi] += dp2[x]) %= mod;
        }
    }
    long long ans = dp[t]*dp[t]%mod, sub = 0;
    for(int x = 1; x <= n; x++){
        for(auto y : e[x]){
            if(ds[x] + y.se + dt[y.fi] != ds[t]) continue;

            if( (ds[x] <= dt[y.fi] && dt[y.fi] < ds[x] + y.se) || (dt[y.fi] < ds[x] && ds[x] < dt[y.fi] + y.se)){
                    //<= orz
                ll temp = dp[x]*dp2[y.fi]%mod;
                (sub += temp*temp%mod) %= mod;
            }
        }
        if(ds[x] == dt[x]) { // orz
            ll temp = dp[x]*dp2[x]%mod;
            (sub += temp*temp%mod) %= mod;
        }
    }
    ((ans -= sub) += mod) %= mod;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 23296
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,y,flag=0;
    cin>>n>>y;
    for (int i=0;i<=y/10000;i++) {
        for (int j=0;j<=(y-i*10000)/5000;j++) {
            int rem=y-(10000*i)-(5000*j);
            if (rem>=0) {
                if ( rem%1000==0&&i+j+rem/1000==n ) {
                    cout<<i<<" "<<j<<" "<<rem/1000<<endl;
                    flag++;
                    break;
                }
            }
        }
        if (flag==1) {
            break;
        }
    }
    if (flag==0) {
        cout<<-1<<" "<<-1<<" "<<-1<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define MOD 1000000007
typedef long long ll;

using namespace std;

int main(void){
  int w, h, x, y, r;
  cin >> w >> h >> x >> y >> r;

  if (x - r < 0 || y - r < 0 || x + r > w || y + r > h) {
    cout << "No" << "\n";
  } else {
    cout << "Yes" << "\n";
  }
}


Measured memory_bytes: 3104
n = int(input())
s = [0]*n
c = [1]*n

for i in range(n):
	s[i] = input()

s.sort()    
    
for i in range(n-1): 
	if s[i] == s[i+1]:
		c[i+1] += c[i]
      
M = max(c)

for i in range(n):
	if c[i] == M:
		print(s[i])

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<ll,ll> P;
typedef tuple<ll,ll> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

map<ll,ll> m;
VL v{2,3,5}, cost;
ll N,A,B,C,D;

ll dfs(ll x){
    if(x == 0) return 0;
    if(x == 1) return D;
    if(m.find(x) != m.end()) return m[x];

    ll ret = LINF;
    REP(i,3){
        ll flr = x/v[i]*v[i], cil = (x+v[i]-1)/v[i]*v[i];
        if(flr>0) chmin(ret, dfs(flr/v[i]) + cost[i] + D*(x-flr));
        chmin(ret, dfs(cil/v[i]) + cost[i] + D*(cil-x));
    }
    if(x <= LINF/D) chmin(ret, D*x);

    return m[x] = ret;
}
void Main(){
    m.clear();
    cin >> N >> A >> B >> C >> D;
    cost.resize(3); cost[0] = A; cost[1] = B; cost[2] = C;
    ll ans = dfs(N);
    cout << ans << en;
    return;
}

int main(void){
    cin.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15);
    int t=1; cin>>t;
    REP(_,t){
        Main();
    }
    return 0;
}

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

bool solve() {
    int H, W;
    cin >> H >> W;
    if(H == 0 && W == 0) return false;
    for(int i = 0; i < H; ++i) {
        for(int j = 0; j < W; ++j) cout << "#" ;
        cout << endl;
    }
    cout << endl;
    return true;
}

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


Measured memory_bytes: 3092
#include <iostream>
#include <bits/stdc++.h>
#include <math.h>

using namespace std;

int main(){
    int h,n;
    cin>>h>>n;
    for(int i=0;i<n;i++){
        int hoge;
        cin>>hoge;
        h-=hoge;
    }
    
    if(h<=0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    
    return 0;
}

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

#define int long long 

main()
{
  int n, k;
  int a[100005];
  int sum = 0;
  int sig;

  cin >> n >> k;
  
  for(int i = 0; i < n; i++) cin >> a[i];
  
  sum += max(0LL, a[0] - k);
  a[0] = min(k, a[0]);
  
  sum += max(0LL, a[n - 1] - k);
  a[n - 1] = min(k, a[n - 1]);
  
  
  sig = a[n - 2] + a[n - 1];
  sum += max(sig - k, 0LL);
  a[n - 2] -= max(sig - k, 0LL);
  
  for(int i = 1; i < n - 1; i++) {
    sig = a[i - 1] + a[i];
    sum += max(sig - k, 0LL);
    a[i] -= max(sig - k, 0LL);
  }
  
  cout << sum << endl;

  return (0);
}
  

  


Measured memory_bytes: 1024
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define brep(index,num) for(int index=num-1;index>=0;index--)
#define brep1(index,num) for(int index=num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int a,b,c;
	scan(a>>b);
	rep1(i,3){
		if(i!=a&&i!=b){
			prin(i);
			return 0;
		}
	}
	return 0;
}


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

int main() {
	int H, W;
	cin >> H >> W;
	string st[100];

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

	for (int i = 0; i < H; i++) {
		cout << st[i] << endl;
		cout << st[i] << endl;
	}

}

Measured memory_bytes: 256
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def bfs(adj, nxt, dis, sumi, kyori):
    nnxt = []
    for u in nxt:
        sumi[u] = True
        dis[u] = kyori

    for u in nxt:
        for v in adj[u]:
            if not sumi[v]:
                nnxt.append(v)

    return nnxt, kyori + 1

def solve():
    n = int(input())
    adj = [None] * n
    for i in range(n):
        u, k, *vs = [int(j) - 1 for j in input().split()]
        adj[u] = vs

    # debug(adj, locals())

    sumi = [False] * n
    dis = [-1] * n
    nxt = [0]
    kyori = 0

    while nxt:
        nxt, kyori = bfs(adj, nxt, dis, sumi, kyori)

    for i in range(n):
        print(i + 1, dis[i])

    pass

if __name__ == '__main__':
    solve()

Measured memory_bytes: 8628
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1000+10;
const ll p=1e9+7;
char a[N][N];
ll base[2][2],t[2][2],ans[2];

inline ll fpm(ll a,ll b)
{
	ll ret=1;
	for(;b;b>>=1) ret=(b&1)?ret*a%p:ret,a=a*a%p;
	return ret;
}

inline void add(ll &a,ll b)
{
	a=a+b>=p?a+b-p:a+b;
}

void mulself(void)
{
	memset(t,0,sizeof(t));
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			for(int k=0;k<2;++k)
				add(t[i][k],base[i][j]*base[j][k]%p);
	memcpy(base,t,sizeof(base));
}

void mul(void)
{
	memset(t[0],0,sizeof(t[0]));
		for(int j=0;j<2;++j)
			for(int k=0;k<2;++k)
				add(t[0][k],ans[j]*base[j][k]%p);
	memcpy(ans,t[0],sizeof(ans));
}

void mpw(ll k)
{
	for(;k;k>>=1,mulself()) if(k&1) mul();
}

int main()
{
	int n,m;ll k;
	scanf("%d %d %lld",&n,&m,&k);
	if(k==0){printf("1\n");return 0;};
	for(int i=1;i<=n;++i) scanf("%s",a[i]+1);
	int cblack=0,crow=0,ccol=0,cpair=0;
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cblack+=a[i][j]=='#';
	for(int i=1;i<=n;++i) crow+=a[i][1]=='#'&&a[i][m]=='#';
	for(int i=1;i<=m;++i) ccol+=a[1][i]=='#'&&a[n][i]=='#';
	if(crow&&ccol) printf("1\n");
	else if(!crow&&!ccol) printf("%lld\n",fpm(cblack,k-1));
	else
	{
		if(crow) 
			for(int i=1;i<=n;++i) for(int j=1;j<m;++j) cpair+=a[i][j]=='#'&&a[i][j+1]=='#';
		else 
			for(int i=1;i<n;++i) for(int j=1;j<=m;++j) cpair+=a[i][j]=='#'&&a[i+1][j]=='#';
		base[0][0]=cblack;base[0][1]=0;base[1][0]=cpair;base[1][1]=crow?crow:ccol;ans[0]=0;ans[1]=1;
		mpw(k-1);
		printf("%lld\n",((fpm(cblack,k-1)-ans[0])%p+p)%p);
	};
	return 0;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
#define md 1000000007
#define ll long long 
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fastmap mp.reserve(1024);mp.max_load_factor(0.25);
#define fastset st.reserve(1024);st.max_load_factor(0.25);
ll int mpw(ll int a,ll int b,ll int m)
{
	ll int ans=1;
	if(a==0)return 0;
	if(a==1 || b==0)return 1;
	while(b)
	{
		if(b&1)
		{
			ans=(ans*a)%m;
		}
		a=(a*a)%m;
		b>>=1;
	}
	return ans;
}

ll int pw(ll int a,ll int b)
{
	ll int ans=1;
	if(a==0)return 0;
	if(a==1 || b==0)return 1;
	while(b)
	{
		if(b&1)
		{
			ans*=a;
		}
		a*=a;
		b>>=1;
	}
	return ans;
}

ll int mn(ll int a,ll int b)
{
	if(a<=b)
	{
		return a;
	}
	return b;
}

ll int mx(ll int a,ll int b)
{
	if(a>=b)
	{
		return a;
	}
	return b;
}
vector<vector<ll int>>D;
int main()
{
	fio
	int n,w;
	cin>>n>>w;
	vector<pair<int,ll int>>nm(n);
	int sm=0;
	for(int i=0;i<n;++i)
	{
		cin>>nm[i].first>>nm[i].second;
		sm+=nm[i].second;
	}
	vector<vector<ll int>>D(n,vector<ll int>(sm+1,-1));
	D[0][0]=0;
	D[0][nm[0].second]=nm[0].first;
	for(int i=1;i<n;++i)
	{
		D[i][0]=0;
		for(int j=1;j<=sm;++j)
		{
			D[i][j]=D[i-1][j];
			if(j>=nm[i].second && D[i-1][j-nm[i].second]!=-1)
			{
				if(D[i][j]==-1)
				{
					D[i][j]=D[i-1][j-nm[i].second]+nm[i].first;
				}
				else{
					D[i][j]=mn(D[i-1][j-nm[i].second]+nm[i].first,D[i][j]);	
				}
			}
		}
	}
	ll int ans=0;
	for(int i=0;i<=sm;++i)
	{
		if(D[n-1][i]!=-1 && D[n-1][i]<=w)
		{
			ans=i;
		}
	}
	cout<<ans<<"\n";
	return 0;
}

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

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

int main(){
  int k;
  cin>>k;
  if(k%2==0)
    cout<<pow(k/2,2)<<endl;
  else
    cout<<(k/2)*(k/2+1)<<endl;



  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()
#define CERR if(false) cerr
#define INT_MAX_HALF (INT_MAX / 2)

typedef long long ll;

using namespace std;
//using namespace boost::multiprec

int main(){

    
    int n;
    cin >> n;

    vector<vector<pair<int, ll >> > edge(n + 1);

    rep(i,n - 1){
        int a,b;
        ll c;
        cin >> a >> b >> c;

        edge[a].pback(mpair(b,c));
        edge[b].pback(mpair(a,c));
    }

    int q,k;
    cin >> q >> k;

    cerr << q << " " << k << endl;

    vector<ll> d(n + 1, LLONG_MAX);

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

    pq.push(mpair(0, k));

    while(!pq.empty()){

        ll tmpd = pq.top().first;
        ll node = pq.top().second;

        if(d[node] > tmpd){
            d[node] = tmpd;

            rep(i, edge[node].size()){
                pq.push(mpair(tmpd + edge[node][i].second, edge[node][i].first));
            }
        }

        pq.pop();
    }

    rep(i,q){

        int x, y;
        cin >> x >> y;

        cout << d[x] + d[y] << endl;
    }

    return 0;
}

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

string d[4] = {"maerd", "remaerd", "esare", "resare"};

int main() {
  string S;
  cin >> S;
  
  bool frag = true;
  reverse(S.begin(), S.end());

  for (int i = 0; i < S.size();) {
    bool can = false;
    for (int j = 0; j < 4; j++) {
      string x = d[j];
      if (x == S.substr(i, x.size())) {
        can = true;
        i += x.size();
      }
    }
    if (!can) {
      frag = false;
      break;
    }
  }
  if (frag) cout << "YES" << endl;
  else cout << "NO" << endl;
}


Measured memory_bytes: 512