akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

#define I inline void 

using ll = long long ; 
using ld = long double ; 

using namespace std ; 

const int N = 3000 + 7 , mod = 1e9 + 7 ; 

int n , m ;

int A[N][N] ; 
ll dp[N][N][4] ; 

ll solve(int i , int j , int k){
	if(i == n -1 && j == m -1 )
		return (k < 3 ? A[i][j] : 0) ; 
	if(i == n || j == m)
		return -1e18 ; 
	if(dp[i][j][k] != -1)
		return dp[i][j][k] ; 
	ll ret = 0 ;
	if(k < 3){
		ret = max(ret , solve(i+1 , j , 0 ) + A[i][j] );
		ret = max(ret , solve(i , j +1 , k +1 ) + A[i][j]) ; 
	}
	ret = max(ret , solve(i+1 , j , 0) ) ; 
	ret = max(ret , solve(i , j + 1 , k)) ; 
	
	return dp[i][j][k] = ret  ;
}

int main(){	
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; 
	ll x , k  ,d ; 
	ll ans = 1e18 ;
	memset(dp , -1 , sizeof dp) ;  
	//freopen("in.in" , "r" , stdin) ;  

	cin >> n >> m >> k ; 
	for(int i = 0 ;i < k ;i++){
		int a , b , c ; 
		cin >> a >> b;  
		a-- ; b-- ; 
		cin >> A[a][b] ; 
	}
	cout<< solve(0 , 0 , 0 ) ; 
	return 0 ; 
}

Measured memory_bytes: 321856
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define forn(i,a,b) for(int i =a;i<b;i++)
#define fi first
#define se second
#define fast ios_base::sync_with_stdio(false);
using namespace std;

typedef long long int ll;
typedef vector<ll> vi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int mxn = 1e5;
// int cnt1[mxn+2],cnt2[mxn+2];

const int modi = 1e9 + 7;
void solve(){
	int n,k;
	cin >> n >> k;
	ll fact[n+1],inv[n+1],ifact[n+1];
	fact[0] = 1;
	inv[1] = 1;
	ifact[0] = 1;
	ifact[1] = 1;
	for(int i =1;i<=n;i++){
		fact[i] = fact[i-1]*i%modi;
	}

	for(int i = 2;i<=n;i++){
		inv[i] = (modi - modi/i*inv[modi%i]%modi)%modi;
	}

	for(int i =2;i<=n;i++){
		ifact[i] = ifact[i-1]*inv[i]%modi;
	}

	auto ncr = [&](int n , int r){
		if(n<r) return 0LL;
		return (fact[n]*ifact[n-r]%modi)*ifact[r]%modi;
	};

	ll ans = 0;
	for(int i =0;i<=min(n,k);i++){
		ans = (ans + ncr(n,i)*ncr(n-1,i)%modi)%modi;
		// cout << ans << endl;
	}
	cout << ans << endl;
}

int main(){
	fast;
	// #ifndef ONLINE_JUDGE
	// 	freopen("input.txt","r",stdin);
	// 	freopen("output.txt","w",stdout);
	// #endif

	// int t;cin >> t;while(t--)
		solve();
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define pb push_back
#define pi pair<int, int>
#define l first
#define r second
#define all(x) x.begin(), x.end()
#define fori(a, b, step) for (int i = a; i < b; i += step)
#define forj(a, b, step) for (int j = a; j < b; j += step)
#define int long long

const int maxn = 1e6 + 1, mod = 1e9 + 7;

using namespace std;

int a[maxn];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, d;
    cin >> n >> d;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int x, y; cin >> x >> y;
        ans += (x * x + y * y <= d * d);
    }
    cout << ans;
    return 0;
}


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

#define ll long long
#define ull unsigned long long

#define min(a, b) ((a) > (b) ? (b) : (a))
#define max(a, b) ((a) > (b) ? (a) : (b))

bool isPalindrome(string s) {
    string t(s.rbegin(), s.rend());
    return s == t;
}

int main(void) {
    ll K;
    ll sum = 0, sum2 = 0;
    cin >> K;
    for(ll i = 1;i <= K;i++) {
        for(ll j = 1;j <= K;j++) {
            for(ll k = 1;k <= K;k++) {
                ll a, b;
                a = __gcd(i, j);
                sum += __gcd(a, k);
            }
        }
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef long long int ll;
typedef unsigned long long int sll;
typedef  double ld;
#define A 1000000007ll
#define D 1000000000ll
#define B 998244353ll
#define C 1000000000000000000ll
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define oset tree<pair<ll,ll>, null_type,less<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
#define pb push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define ve vector
#define br break
#define PI 3.14159265358979323
#define subt cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n"

ll dp[7007];

int main() 
{
    FAST;
    ll n,t;
    cin>>n>>t;
    pair<ll,ll> a[n];
    ll x,y;
    for(int i=0;i<n;i++)
    {
        cin>>x>>y;
        a[i]={x,y};
    }
    sort(a,a+n);
    for(int i=1;i<7007;i++)
        dp[i]=-1;
    for(int i=0;i<n;i++)
        for(int j=t-1;j>=0;j--)
            if(dp[j]!=-1)
                dp[a[i].first+j]=max(dp[a[i].first+j],dp[j]+a[i].second);
    ll ans=0;
    for(int i=0;i<7007;i++)
        ans=max(ans,dp[i]);
    cout<<ans;
    subt;   
    return 0;
}

Measured memory_bytes: 384
N = int(input())
Hs = list(map(int, input().split()))
movements = [0]
nmove = 0
Hf = Hs[0]
for i in range(N):
    if i == 0:
        Hf = Hs[i]
    else:
        if Hf>=Hs[i]:
            nmove += 1
            if i == N-1:
                movements.append(nmove)
        else:
            movements.append(nmove)
            nmove = 0
        Hf = Hs[i]
print(max(movements))

Measured memory_bytes: 14252
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
 
const int MOD = 998244353;
int N, S;
vector<int> v;
int dp[3005][3005];
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> S;
	v.resize(N);
	for (int i = 0; i < N; i++) cin >> v[i];
 
	//f(i, j)=k인 0 <= j <= i의 개수
	// 점화식 dp[i][j] = dp[i-1][j] + dp[i-1][j-v[i]] % MOD
	// 기저사례 dp[i][0] = 1
 
	int ans = 0;
	for (int i = 0; i < N; i++) dp[i][0] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= S; j++) {
			dp[i + 1][j] += dp[i][j];
			dp[i + 1][j] %= MOD;
		}
		for (int j = v[i]; j <= S; j++) {
			dp[i + 1][j] += dp[i][j - v[i]];
			dp[i + 1][j] %= MOD;
		}
//		cout << dp[i + 1][S] << '\n';
 
		ans += dp[i + 1][S];
		ans %= MOD;
	}
 
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 35456
using System;

namespace AizuOnline
{
    class Program
    {
        static void Main()
        {
            string[] nums = Console.ReadLine().Split();
            int a = Int32.Parse(nums[0]);
            int b = Int32.Parse(nums[1]);
            int c = Int32.Parse(nums[2]);
            if (a < b && b < c)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 8836
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
VI e[SIZE];
int v[SIZE],be;
PII re[SIZE];
PII dfs(int x,int pa,int od){
    PII me=MP(-MOD,MOD);
    if(v[x]!=-1){
        me=MP(v[x],v[x]);
        if(be==-1)be=(v[x]&1)^od;
        else if(be!=((v[x]&1)^od)){
            puts("No");
            exit(0);
        }
    }
    REP(i,SZ(e[x])){
        int y=e[x][i];
        if(y==pa)continue;
        PII ret=dfs(y,x,od^1);
        me.F=max(ret.F-1,me.F);
        me.S=min(ret.S+1,me.S);
    }
    if(me.F>me.S){
        puts("No");
        exit(0);
    }
    return re[x]=me;
}

PII go(int x,int pa){
    if(v[x]==-1)v[x]=re[x].F;
    REP(i,SZ(e[x])){
        int y=e[x][i];
        if(y==pa)continue;
        re[y].F=max(re[y].F,v[x]-1);
        re[y].S=min(re[y].S,v[x]+1);
        go(y,x);
    }
}
int main(){
    be=-1;
    DRI(N);
    REPP(i,1,N){
        DRII(x,y);
        e[x].PB(y);
        e[y].PB(x);
    }
    DRI(M);
    MS1(v);
    REP(i,M){
        DRII(x,y);
        v[x]=y;
    }
    PII ret=dfs(1,1,0);
    go(1,1);
    puts("Yes");
    REPP(i,1,N+1)printf("%d\n",v[i]);
    return 0;
}


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

typedef long long ll;
const int N = 4e2+5;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n;
ll dp[N][N] , val[N][N];

int main(){

  cin >> n;
  for(int i = 1 ; i <= n ; i++) cin >> val[i][i];
  for(int i = 1 ; i <= n ; i++)
    for(int j = 1 ; j <= n ;j++)
      if(i != j) dp[i][j] = inf;

  for(int i = 1 ; i <= n ; i++){
    for(int j = i-1 ; j > 0 ; j--){
      for(int z = j ; z < i ; z++){
        if(dp[j][i] > dp[j][z] + dp[z+1][i] + val[j][z] + val[z+1][i]){
          val[j][i] = val[j][z] + val[z+1][i];
          dp[j][i] = dp[j][z] + dp[z+1][i] + val[j][z] + val[z+1][i];
        }
      }
    }
  }

  cout << dp[1][n] << "\n";

}


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

typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<ll,ll> Pll;

#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define repp(i, n) for(int i=1;i<=n;i++)
#define all(x) x.begin(), x.end()

#define geti1(X) scanf("%d",&X)
#define geti2(X,Y) scanf("%d%d",&X,&Y)
#define geti3(X,Y,Z) scanf("%d%d%d",&X,&Y,&Z)
#define geti4(X,Y,Z,W) scanf("%d%d%d%d",&X,&Y,&Z,&W)

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define geti(...) GET_MACRO(__VA_ARGS__, geti4, geti3, geti2, geti1) (__VA_ARGS__)

#define INF 7654321
#define IINF 87654321987654321LL
#define MAXV 200500

ll mod = 1e9 + 7;


int main(){
	int a,b; geti(a,b);
	if( a%b == 0 ) {
		printf("-1\n");
		return 0;
	}
	printf("%d\n",a);
}


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

#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 rer(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))

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int inf = 1000000000;
const int mod = 1000000007;
const double eps = 1e-9;
const int dx[] = { -1, 0, 1, 0};
const int dy[] = { 0, -1, 0, 1};

int main() {
	// cin.tie(0); // tie
	// ios::sync_with_stdio(false); // sync
	int N, Q;
	while (cin >> N >> Q, N || Q) {
		vector<int> data(100);
		rep(i, N) {
			int M; cin >> M;
			rep(j, M) {
				int d;
				cin >> d; d--;
				data[d]++;
			}
		}

		int ans = 0;
		rep(i, 100) if (data[ans] < data[i]) ans = i;
		if (data[ans] >= Q) cout << ans + 1 << endl;
		else cout << 0 << endl;
	}
	return 0;
}

Measured memory_bytes: 1196
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
int main(){
    int x;
    cin >> x;
    if (x == 7 || x == 5 || x == 3)cout << "YES";
    else cout << "NO";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const double inf=1e18;
int n,belong[1005],dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},t[100005];
double x[100005],y[100005];
char s[5];
double f(double xx) {
	double xmi=inf,xmx=-inf,ymi=inf,ymx=-inf;
	for (int i=1; i<=n; i++) {
		xmi=min(xmi,x[i]+dx[t[i]]*xx);
		xmx=max(xmx,x[i]+dx[t[i]]*xx);
		ymi=min(ymi,y[i]+dy[t[i]]*xx);
		ymx=max(ymx,y[i]+dy[t[i]]*xx);
	}
	return (xmx-xmi)*(ymx-ymi);
}
int main() {
	belong['R']=0;
	belong['L']=1;
	belong['U']=2;
	belong['D']=3;
	scanf("%d", &n);
	for (int i=1; i<=n; i++) {
		scanf("%lf%lf%s", &x[i], &y[i], s);
		t[i]=belong[s[0]];
	}
	double l=0,r=1e9,lmid,rmid,L,R,res=inf;
	for (int i=0; i<200; i++) {
		lmid=(l*2+r)/3;
		rmid=(l+r*2)/3;
		L=f(lmid),R=f(rmid);
		res=min(res,min(L,R));
		if (L>R) l=lmid;
		else r=rmid;
	}
	printf("%.15f\n", res);
	return 0;
}

Measured memory_bytes: 2176
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  vector<string> S(3);
  rep(i,3) cin >> S[i];
  vector<char> ans = {'A', 'B', 'C'};
  vector<int> itr(3,0);
  int turn = 0;
  while(1){
    // cout << itr[0] << itr[1] << itr[2] << endl;
    if(itr[turn] == S[turn].size()){
      cout << ans[turn] << endl;
      break;
    }
    int next = (int)(S[turn][itr[turn]]-'a');
    itr[turn]++;
    turn = next;
  }

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
	string s;
	cin>>s;
	string t="CODEFESTIVAL2016";
	int ans=0;
	rep(i,16)ans+=(s[i]!=t[i]);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

import collections

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

c = collections.Counter(A)
values = c.keys()
counts = c.values()

subs = {}
a_sum = 0
for v, c in zip(values, counts):
    subs[v] = c
    a_sum += (c * (c-1)) // 2

for i in range(N):
    print(a_sum - subs[A[i]] + 1)


Measured memory_bytes: 32156
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;


namespace ABC137
{
    class Program
    {
        static void Main(string[] args)
        {
            var cin = ReadInts();
            var a = cin[0];
            var b = cin[1];
            var puls = a + b;
            var minus = a - b;
            var mul = a * b;
            var maxnum = (puls > minus) ? puls : minus;
            maxnum = (maxnum > mul) ? maxnum : mul;

            WriteLine("{0}", maxnum);
            Read();
        }

        private static string Read() { return ReadLine(); }
        private static char[] ReadChars() { return Array.ConvertAll(Read().Split(), a => a[0]); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


Measured memory_bytes: 13268
#include<iostream>
#include<vector>

using namespace std;

int ans[100];
int cont = 0;

int main()
{
	for(;;){
		int n;		//[ÌÎÛÆÈé£ZÒÌ
		int m;		//Dµ½£ZÒÌÔ
		double p;		//T¦
		int temp;
		
		int total = 0;	//S[Ìvàz
		
		cin >> n;
		cin >> m;
		cin >> p;
		
		if(n == 0 && m == 0 && p == 0){
			break;
		}
		
		vector<int> ken(n,0);
		
		for(int i = 0; i < n; i++){
			cin >> ken[i];
		}
		
		/*  vàz±o  */
		for(int i = 0; i < n; i++){
			total += ken[i]*100;
		}
		
		total = total*((100-p)/100);
		
		if(ken[m-1] == 0){
			total = 0;
		}
		else{
			total = total / ken[m-1];
		}
		
	//	cout << total << endl;
		ans[cont] = total;
		
		cont++;
	}
	
	for(int i = 0; i < cont; i++){
		cout << ans[i] << endl;
	}
	
}
	

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

int main() {
    int N ;
    cin >> N ;
    
    vector<long long > A(N) ;
    
    for( int i=0; i<N ; i++){
        cin >> A.at(i) ;
    }
    
    long long cnt=0 ;
    
    
    
    for( int i=0 ; i<(N-1) ; i++){
        if( A.at(i) > A.at(i+1) ){
            cnt += ( A.at(i) - A.at(i+1) ) ;
            A.at(i+1) = A.at(i) ;
        }
    }
    
    cout << cnt << endl;
}


Measured memory_bytes: 4840
#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 ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const ld 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;
    string S, L, R;
    cin >> N >> S;
    rep(i, N) L += S[i], R += S[2*N-1-i];
    ll ans = 0;
    map<pair<string, string>, ll> mp;
    rep(i, 1<<N){
        string a, b;
        rep(j, N){
            if(i & (1<<j)) a += R[j];
            else b += R[j];
        }
        mp[make_pair(a, b)]++;
    }
    rep(i, 1<<N){
        string a, b;
        rep(j, N){
            if(i & (1<<j)) a += L[j];
            else b += L[j];
        }
        ans += mp[make_pair(a, b)];
    }
    cout << ans << endl;
}

Measured memory_bytes: 91904
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N = 100010;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
typedef long long ll;
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(auto &t:a)cin>>t;return i;}
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T> void prArr(T a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}

ll mod_pow(ll x,ll n){
  ll res=1;
  while(n){
    if(n%2) res=res*x%mod;
    x=x*x%mod;
    n/=2;
  }
  return res;
}

vector<vector<P> > G;
vector<int> dijkstra(int S,int T){
  int n = G.size();
  priority_queue<P,vector<P>,greater<P> >Q;
  vector<int> D(n,INF);
  D[S] = 0;
  Q.push(P(0,S));
  while(!Q.empty()){
    auto p = Q.top();Q.pop();
    int pos = p.second;
    int cost = p.first;
    
    if(D[pos] < cost) continue;
    
    for(auto p:G[pos]){
      int to = p.first;
      int ncost = cost + p.second;
      if(D[to] <= ncost) continue;
      D[to] = ncost;
      Q.push(P(ncost,to));
    }
  }
  return D;
}

vector<int> dijkstra_cnt(int S,int T,vector<int> D,vector<int> D2){
  int n = G.size();
  priority_queue<P,vector<P>,greater<P> >Q;
  D[S] = 0;
  Q.push(P(0,S));
  vector<int> cnt(n);
  vector<int> used(n);
  cnt[S] = 1;
  while(!Q.empty()){
    auto p = Q.top();Q.pop();
    int pos = p.second;
    int cost = p.first;
    
    if(used[pos]++) continue;
    
    for(auto p:G[pos]){
      int to = p.first;
      int ncost = cost + p.second;
      if(D[pos] + D2[to] + p.second != D[T]) continue;
      cnt[to] = (cnt[to] + cnt[pos])%mod;
      Q.push(P(ncost,to));
    }
  }
  return cnt;
}

signed main(){
  int n,m;
  cin>>n>>m;
  int S,T;
  cin>>S>>T; S--,T--;

  G.resize(n);
  for(int i=0;i<m;i++){
    int u,v,d;
    cin>>u>>v>>d; u--,v--;
    G[u].push_back(P(v,d));
    G[v].push_back(P(u,d));
  }

  vector<int> D1 = dijkstra(S,T);
  vector<int> D2 = dijkstra(T,S);
  vector<int> cnt1 = dijkstra_cnt(S,T,D1,D2);
  vector<int> cnt2 = dijkstra_cnt(T,S,D2,D1);

  int ans = cnt1[T]*cnt1[T]%mod;
  for(int i=0;i<n;i++){
    if(D1[T] != D1[i]*2) continue;
    int a = cnt1[i] * cnt2[i] % mod;
    a = a * a %mod;
    ans = (ans + mod -a) % mod;
  }

  for(int i=0;i<n;i++)
    for(auto t:G[i]){
      int to = t.first;
      int cost = t.second;
      if(D1[i] + D2[to] + cost != D1[T]) continue;
      if(D1[i]*2 < D1[T] && D1[to]*2 > D1[T]) {
        int a = cnt1[i] * cnt2[to] % mod;
        a = a * a %mod;
        ans = (ans + mod -a) % mod;
      }
    }
  cout<<ans<<endl;
  return 0;
}


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

using namespace std;

struct expand_type {
    template <typename... T>
    expand_type (T&&...) {}
};
template <typename... ArgTypes>
void print (ArgTypes... args) {
    expand_type {0, (cerr << args << ", ", 0)...};
    cerr << "\b\b \n";
}
#define printv(x) cerr << "["; for(auto i : (x)) cerr << i << ", "; cerr << "\b\b]\n";
#define __lcm(a,b) a * b / __gcd(a, b)

typedef unsigned long long ull;
typedef long double ld;



int main () {
    std::ios::sync_with_stdio (false);
    cin.tie (nullptr);
    cout.tie (nullptr);
    int a,b;
    cin >> a >> b;
    cout << a*b;
    return 0;
}


Measured memory_bytes: 3652
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FS r = new FS();
		for(int i=0; i<3; i++) {
			System.out.print(""+r.next().charAt(0));
		}
		System.out.println();
	}

	// Read Class
	static class FS {
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;
		private boolean hasNextByte() {
			if (ptr < buflen) {
				return true;
			} else {
				ptr = 0;
				try {
					buflen = in.read(buffer);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (buflen <= 0) {
					return false;
				}
			}
			return true;
		}

		private int readByte() { return hasNextByte() ? buffer[ptr++] : -1;}
		private boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}
		private void skipUnprintable() {while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}

		public boolean hasNext() { skipUnprintable(); return hasNextByte();}
		public String next() {
			if (!hasNext()) throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while(isPrintableChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}
		public int nextInt() {
			return (int)nextLong();
		}
		public long nextLong() {
			if (!hasNext()) throw new NoSuchElementException();
			long n = 0;
			boolean minus = false;
			int b = readByte();
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			if (b < '0' || '9' < b) {
				throw new NumberFormatException();
			}
			while(true) {
				if ('0' <= b && b <= '9') {
					n *= 10;
					n += b - '0';
				} else if(b == -1 || !isPrintableChar(b)) {
					return minus ? -n : n;
				} else {
					throw new NumberFormatException();
				}
				b = readByte();
			}
		}
	}
}


Measured memory_bytes: 8276
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    string s;
    cin >> s;
    set<char> st;
    st.insert(s[0]);
    st.insert(s[1]);
    st.insert(s[2]);
    if ((int)st.size() == 1) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;
 
const ll nmax = 1e9 + 7;
const ll Mod = 998244353;
const double PI = 2 * asin(1);

int main(){
  int N; cin >> N;
  int X[N], M[N];
  for (int i = 0; i < N; i++) {
    cin >> X[i]; M[i] = X[i];
  }
  sort(M, M + N);
  int m1 = M[N / 2 - 1], m2 = M[N / 2];
  for (int i = 0; i < N; i++){
    if (X[i] <= m1) cout << m2 << endl;
    else cout << m1 << endl;
  }

  return 0;
}


Measured memory_bytes: 3712
def resolve():
    n = int(input())
    if n < 600:
        print(8)
    elif n < 800:
        print(7)
    elif n < 1000:
        print(6)
    elif n < 1200:
        print(5)
    elif n < 1400:
        print(4)
    elif n < 1600:
        print(3)
    elif n < 1800:
        print(2)
    elif n < 2000:
        print(1)

resolve()

Measured memory_bytes: 61716
fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(' ').map(String::toInt)
    val psList = mutableListOf<Pair<Int, String>>()
    (1..m).forEach {
        val (p, s) = readLine()!!.split(' ')
        psList.add(Pair(p.toInt(), s))
    }
    psList.sortBy { it.first }
    val acList = IntArray(n+1){0}
    val waList = IntArray(n+1){0}
    for(i in 0 until m){
        val (p,s) = psList[i]
        if(s=="AC" && acList[p]==0){
            acList[p]=1
        }
        if(s =="WA" && acList[p]==0){
            waList[p]++
        }
    }

    var acCount = 0L
    var waCount = 0L
    for(i in 1..n){
        if(acList[i]>0){
            acCount++
            waCount+=waList[i]
        }
    }
    println("$acCount $waCount")
}

Measured memory_bytes: 80384
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define vi vector <int>
#define vvi vector <vi>
#define ll long long
#define vll vector <ll>
#define vvl vector <vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ep emplace
#define fs first
#define sd second
#define mod 998244353
#define EPS 1e-9
using namespace std;

int main() {
	FIO;
	ll a, b, c;
	cin >> a >> b >> c;
	ll x = c - a - b;
	bool t;
	if (x < 0) t = 0;
	else t = (4 * a * b < x * x);
	cout << (t ? "Yes\n" : "No\n");
	return 0;
}


Measured memory_bytes: 384
'''

'''

INF = float('inf')

def main():
    H, W, K = map(int, input().split())
    S = [input() for _ in range(H)]
    S = [''.join(S[row][col] for row in range(H)) for col in range(W)]
    ans = INF
    for b in range(0, 2**H, 2):
        sections = [(0, H)]
        for shift in range(1, H):
            if (1<<shift) & b:
                sections.append((sections.pop()[0], shift))
                sections.append((shift, H))
        t_ans = len(sections) - 1
        count = {(l, r): 0 for l, r in sections}
        for col in range(W):
            if any(count[(l, r)] + S[col][l:r].count('1') > K for l, r in sections):
                for key in count.keys():
                    count[key] = 0
                t_ans += 1
            for l, r in sections:
                count[(l, r)] += S[col][l:r].count('1')
            if max(count.values()) > K:
                t_ans = INF
                break
        ans = min(ans, t_ans)
    print(ans)


main()


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

int main(){
	int n,in;
	int i;
	while(cin>>n && n!=0){
		int k[7]={0};
		for(i=0;i<n;i++){
			cin>>in;
			if(in>60) in=60;
			(k[in/10])++;
			}
		for(i=0;i<7;i++){
			cout<<k[i]<<endl;
		}
	}
	return 0;
}

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

int getRightIndex(int i);
int getLeftIndex(int i);
void maxHeapify(int a[], int i);
void buildMaxHeap(int a[]);

int H;

int main(void)
{
	cin >> H;
	int *a = new int[H];
	for (int i = 0; i < H; i++) cin >> a[i];

	buildMaxHeap(a);

	for (int i = 0; i < H; i++) cout << " " << a[i];
	cout << endl;

	return 0;
}

int getRightIndex(int i)
{
	return (i + 1) * 2;
}

int getLeftIndex(int i)
{
	return getRightIndex(i) - 1;
}

void maxHeapify(int a[], int i)
{
	int l = getLeftIndex(i);
	int r = getRightIndex(i);
	int largest = i;

	if (l < H && a[l] > a[largest]) largest = l;
	if (r < H && a[r] > a[largest]) largest = r;
	
	if (largest != i) {
		swap(a[i], a[largest]);
		maxHeapify(a, largest);
	}
}

void buildMaxHeap(int a[])
{
	for (int i = (H + 1) / 2 - 1; i >= 0; i--) maxHeapify(a, i);
}

Measured memory_bytes: 5008
#include<bits/stdc++.h>
#define U [1<<17]={}
typedef long long L;using namespace std;map<L,L>T U;L P U,E U,Z U,H U,C U,A U,O U,X U,B U,k,n,a,b,c,p;char s U;
L D(L a){L d;Z[a]=1;for(map<L,L>::iterator I=T[a].begin();I!=T[a].end();I++)
    d=I->first,d-P[a]?P[d]=a,E[d]=E[a]+1,C[d]=I->second,D(d),Z[a]+=Z[d],!H[a]|Z[H[a]]<Z[d]?H[a]=d:0:0;}
#define G(a)((c=A[a]+A[P[a]]+C[a])%k?c:0)
L M(L i){return i?B[i]+M(i^i&-i):0;}
L S(L x,L i){for(x=G(x)+M(i++)-M(i);i<1<<17;i+=i&-i)B[i]+=x;}
L K(L a){p=X[a];n=X[b];return p-n?E[p]<E[n]?swap(p,n),swap(a,b),0:0,M(O[a])-M(O[p])+G(p)+K(P[p]):abs(M(O[a])-M(O[b]));}
main(){for(cin>>n>>k;++p<n;T[a][b]=T[b][a]=c)cin>>a>>b>>c;
       for(D(b=p=0);p<n;p++)if(!p|H[P[p]]-p)for(a=p;!b|a;S(a=H[a],O[a]=b++))X[a]=p;
       for(cin>>a;cin>>s>>a>>b;*s&2?cout<<K(a)<<endl,0:A[a]+=b,S(H[a],O[a]),a?S(a,O[a]-1):0);}

Measured memory_bytes: 33464
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXLOG = 60;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, a[MAXN], f[MAXN], nxt[MAXN];
int dest[MAXN][MAXLOG]; ll k;
int main() {
	read(n), read(k);
	for (int i = 1; i <= n; i++)
		read(a[i]);
	for (int i = n; i >= 1; i--)
		f[a[i]] = i;
	for (int i = n; i >= 1; i--) {
		nxt[i] = f[a[i]];
		f[a[i]] = i;
	}
	dest[0][0] = 1;
	for (int i = n; i >= 1; i--) {
		if (nxt[i] <= i) {
			if (nxt[i] == n) dest[i][0] = 0;
			else dest[i][0] = nxt[i] + 1;
		} else {
			if (nxt[i] == n) dest[i][0] = 1;
			else dest[i][0] = dest[nxt[i] + 1][0];
		}
	}
	for (int p = 1; p < MAXLOG; p++)
	for (int i = 0; i <= n; i++)
		dest[i][p] = dest[dest[i][p - 1]][p - 1];
	int ans = 0;
	for (int i = 0; i < MAXLOG; i++)
		if (k & (1ll << i)) ans = dest[ans][i];
	memset(f, 0, sizeof(f));
	static int b[MAXN]; int tot = 0;
	if (ans == 0) return 0;
	for (int i = ans; i <= n; i++)
		if (f[a[i]] == 0) {
			b[++tot] = a[i];
			f[a[i]] = tot;
		} else {
			int pos = f[a[i]];
			while (tot >= pos) f[b[tot--]] = 0;
		}
	for (int i = 1; i <= tot; i++)
		printf("%d ", b[i]);
	return 0;
}

Measured memory_bytes: 51456
#include <stdio.h>

int main(int argc, char const *argv[]) {
	char str[101];
	int n, m;

	fgets(str, 100, stdin);
	sscanf(str, "%d %d\n", &n, &m);

	if (n + m == 15) {
		printf("+\n");
	} else if (n * m == 15) {
		printf("*\n");
	} else {
		printf("x\n");
	}

	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vll = vector<vl>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const int INF = 2e9;
template<class T> void print(const T& t){ cout << t << endl; }
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; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
  ll m, d;
  cin >> m >> d;
  ll count = 0;
  for (ll i = 22; i <= d; i++){
    ll a = i / 10;
    ll b = i % 10;
    if(b==9){
      i += 2;
    }
    if(a*b<=m){
      count++;
    }
  }
  print(count);
}


Measured memory_bytes: 3616
#include <iostream>
using namespace std;
int d[101] = {},f[101];
int a[101][101];
int kosu[101];
int joutai = 0;
void dfs(int x){
	joutai++;
	d[x] = joutai;
	for(int i = 1;i <= kosu[x];i++){
		if(d[a[x][i]] == 0){
			dfs(a[x][i]);
		}
	}
	joutai++;
	f[x] = joutai;
}

int main(){
	int n,x;
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> x;
		cin >> kosu[x];
		for(int j = 1;j <= kosu[x];j++){
			cin >> a[x][j];
		}
	}
	for(int i = 1;i <= n;i++){
		if(d[i] == 0){
			dfs(i);	
		}	
	}

	for(int i = 1;i <= n;i++){
		cout << i << " " << d[i] << " " <<f[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 1200
#![allow(non_snake_case, unused_imports)]

// Input
macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); let mut next = || { iter.next().unwrap() }; input_inner!{next, $($r)*} }; ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect() }; input_inner!{next, $($r)*} }; }
macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} };}
macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::<Vec<char>>() }; ($next:expr, bytes) => { read_value!($next, String).into_bytes() }; ($next:expr, usize1) => { read_value!($next, usize) - 1 }; ($next:expr, $t:ty) => { $next().parse::<$t>().expect("Parse error") }; }

// Module
use std::cmp::{min,max};
use std::collections::{HashSet,BTreeMap,VecDeque};

// Functions

// Main
fn main(){
    input!{
        N: usize,
        K: usize,
        D: [String; K],
    }
    for i in N..100000{
        if i.to_string().chars().all(|x| !D.contains(&x.to_string())){
            println!("{}", i);
            return;
        }
    }
}

Measured memory_bytes: 4352
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define MIN(x, y) ((x) <= (y) ? (x) : (y))

// just implement simple queue
typedef struct QueueKey {
    char str[16];
    int num;
} QueueKey;
typedef struct QueueDat {
    QueueKey key;
    struct QueueDat *next;
} QueueDat;
typedef struct Queue {
    size_t len;
    QueueDat *head;
    QueueDat *tail;
} Queue;
#define queue_init(q) ((q) ? ((q)->len = 0, (q)->head = (q)->tail = NULL) : 0)
#define queue_len(q) ((q) ? (q)->len : 0)
void queue_push(Queue *q, QueueKey x) {
    QueueDat *new_dat = malloc(sizeof(QueueDat));
    *new_dat = (QueueDat){x, NULL};
    if(q->len) {
        q->tail->next = new_dat;
        q->tail = new_dat;
    }else{
        q->head = q->tail = new_dat;
    }
    q->len++;
}
QueueKey queue_pop(Queue *q) {
    assert(q->len);
    QueueDat *old_head = q->head;
    q->head = old_head->next;
    QueueKey key = old_head->key;
    free(old_head);
    q->len--;
    return key;
}
// <- queue

int main(int argc, char **argv) {
    int n, q;
    scanf("%d%d", &n, &q);
    Queue Q;
    queue_init(&Q);
    QueueKey key;
    for(int i = 0; i < n; ++i) {
        scanf("%s%d", key.str, &key.num);
        queue_push(&Q, key);
    }
    int cnt = 0;
    // while Q is not empty
    while(queue_len(&Q)){
        key = queue_pop(&Q);
        cnt += MIN(key.num, q);
        // if key time bt q, re-push
        if(key.num > q){
            key.num -= q;
            queue_push(&Q, key);
        } else {
            printf("%s %d\n", key.str, cnt);
        }
    }
    return 0;
}



Measured memory_bytes: 4084
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

vector<int> pre, in, post;

int pos = 0;

void constructPost(int l, int r) {
	if (l >= r)
		return;

	int root = pre[pos++];
	int m = distance(in.begin(), find(in.begin(), in.end(), root));
	constructPost(l, m);
	constructPost(m + 1, r);

	post.push_back(root);
}

int main() {

	int n;
	scanf("%d", &n);

	int v;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &v);
		pre.push_back(v);
	}
	for (int i = 0; i < n; ++i) {
		scanf("%d", &v);
		in.push_back(v);
	}


	constructPost(0, pre.size());

	int i = 0;
	for (auto itr = post.begin(); itr != post.end(); ++itr) {
		if (i)
			cout << " ";
		cout << *itr;
		++i;
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 3152
#include <stdio.h>
#include <string.h>
 
int main(void){
  int a[5];
  int n;
  int k = 0;
  scanf("%d",&a[0]);
  scanf("%d",&a[1]);
  scanf("%d",&a[2]);
  scanf("%d",&a[3]);
  scanf("%d",&a[4]);
  
  for(n=0;n<5;n++){
    while(1){
      if(a[n]>10){
        a[n]=a[n]-10;
        k=k+10;
        //printf("%d",k);
      }else{
        break;
      }
    }
  }
  int i,tmp,j;
  for (i = 1; i < n; i++) {
    tmp = a[i];
    if (a[i - 1] > tmp) {
        j = i;
        do {
            a[j] = a[j - 1];
            j--;
        } while (j > 0 && a[j - 1] > tmp);
        a[j] = tmp;
    }
  }
  k=k+40+a[0];
  printf("%d",k);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

ll ceil(ll a, ll b) {  // a÷b以上の最小の整数
    if(a%b == 0) {
        return a/b;
    }
    else {
        return a/b + 1LL;
    }
}

int main() {
    ll k, a, b;
    cin >> k >> a >> b;

    if(k <= a) {
        cout << 1 << endl;
        return 0;
    }

    if(a <= b) {
        cout << -1 << endl;
        return 0;
    }

    ll c = a-b;
    ll ans = 2LL*ceil(k-a, c) + 1LL;

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

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

int b = 0, c = 1e9 + 7 ;
vector<string>vc={"SUN","MON","TUE","WED","THU","FRI","SAT"};
int main ( ){
    string s ;
    cin >> s ;
    if(s==vc[6]){
        cout<<1;
    }
    if (s==vc[5]){
        cout<<2;
    }
    if ( s==vc[4]){
        cout<<3;
    }
    if(s==vc[3]){
        cout<<4;
    }
    if(s==vc[2]){
        cout<<5;
    }
    if(s==vc[1]){
        cout<<6;
    }
    if(s==vc[0]){
        cout<<7;
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<map>

using namespace std;

int main() {
    int a;

    cin>>a;

    if(a/100==1){
        cout<<9;
    }
    else{
        cout<<1;
    }
    a%=100;
    if(a/10==1){
        cout<<9;
    }
    else{
        cout<<1;
    }
    if(a%10==1){
        cout<<9;
    }
    else{
        cout<<1;
    }
	return 0;
}

Measured memory_bytes: 764
n = int(input())
s = input()
count = 0
#print(n)
if n%2==1:
    print("No")
else:
    for i in range(n//2):
        #print(s[i], s[n//2+i])
        if s[i]!=s[n//2+i]:
            count = 1
    if count == 0:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 2940
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    G[a-1].append((b-1,c))
    G[b-1].append((a-1,c))
q,k=map(int,input().split())
k=k-1
stack=[k]
dis=[-1]*n
dis[k]=0
while len(stack)>0:
    now=stack.pop()
    d=dis[now]
    for i in G[now]:
        if dis[i[0]]==-1:
            dis[i[0]]=d+i[1]
            stack.append(i[0])
for i in range(q):
    x,y=map(int,input().split())
    x=x-1
    y=y-1
    print(dis[x]+dis[y])



Measured memory_bytes: 79904
h,w=map(int,input().split())
h3=h//3
h3a=h%3
w3=w//3
w3a=w%3

ans = min((((h3-(-h3a//2)))-h3)*w,  (((w3-(-w3a//2))-w3)*h))

h2 = h//2
w2 = w//2
h2a=h%2
w2a=w%2

ans=min(ans, abs((h3)*w-(w2+w2a)*(h-h3)), abs((h3-(-h3a//2))*w-w2*(h-(h3-(-h3a//2)))))
ans = min(ans, abs((w3)*h-(h2+h2a)*(w-w3)), abs((w3-(-w3a//2))*h-h2*(w-(w3-(-w3a//2)))))

print(ans)


Measured memory_bytes: 38384
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    A = list(map(int, input().split()))

    if 0 in A:
        print(0)
        return

    ans = 1
    n = 10 ** 18
    for i in A:
        ans *= i
        if ans > n:
            print(-1)
            return
    print(ans)


main()


Measured memory_bytes: 21648
#include <bits/stdc++.h>
using namespace std;
int bd[3001][3001], a, b;
string s, t, ans; 

int main() {
	cin >> s >> t;
	s = '?'+s;
	t = '?'+t;

	bd[0][0] = 0;
	for (int i=1; i<t.length(); i++) {
		bd[0][i] = 0;
	}
 	for (int i=1; i<s.length(); i++) {
		bd[i][0] = 0;
	}

	for (int i=1; i<s.length(); i++) {
		for (int j=1; j<t.length(); j++) {
			bd[i][j] = max(bd[i-1][j], bd[i][j-1]);
			if (s[i]==t[j])
				bd[i][j] = max(bd[i][j], bd[i-1][j-1]+1);
		}
	}
	
	ans = "";
	a = s.length()-1;
	b = t.length()-1;
	while (bd[a][b]) {
		if (bd[a-1][b]==bd[a][b])
			a--;
		else if (bd[a][b-1]==bd[a][b])
			b--;
		else {
			ans = s[a]+ans;
			a--;
			b--;
		}	
	}
	cout << ans << "\n";
	return 0;				  
}

Measured memory_bytes: 35456
n=int(input())
li = [0] * 100 # li[top][bottom]
for i in range(1,n+1):
  top = str(i)[0]
  bottom = str(i)[-1]
  if top != 0 and bottom != 0:
    li[int(top+bottom)] += 1

ans=0
for i in range(1,10):
  for j in range(1,10):
    ans += li[10*i+j] * li[10*j+i]

print(ans)

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

signed main(){
    Int N;
    cin>>N;
    vector<Int> A(N);
    for(Int i = 0; i < N; i++){
        cin >> A.at(i);
    }

    Int sum = 0;
    for(Int i = 0; i < N; i++){
        if(A.at(i) < 0){
            sum++;
        }
    }

    Int tmp = 0;
    for(Int i = 0; i < N; i++){
        tmp += abs(A.at(i));
    }

    Int temp = 0;
    Int ans = INT_MAX;
    for(Int i = 0; i < N; i++){
        temp = abs(A.at(i));
        if(temp < ans){
            ans = temp;
        }
    }

    if(sum % 2 == 0){
        cout << tmp << endl;
    }else{
        cout << tmp - ans*2 << endl;
    }
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <string.h>

int main(void)
{
	int i;
	int num;
	char str1[1001+1];
	char str2[] = "Hoshino";
	char *ret;
	char *point;
	
	scanf("%d",&num);
	fgets(str1, sizeof(str1), stdin);
	
	for(i = 0; i < num; i++){
		fgets(str1, sizeof(str1), stdin);
		point = str1;
		while((ret = strstr(point , str2)) != NULL){
			ret[6] = 'a';
			point = ret + 7;
		}
		printf("%s",str1);
	}

	return 0;
}

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


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

  vector<int64_t> t(n);
  for(int i=0;i<n;i++){
    cin>>t.at(i);
  }

  int64_t m;
  cin>>m;

  for(int i=0;i<m;i++){
    int64_t p,x;
    cin>>p>>x;

    int64_t sum=0;
    for(int j=0;j<n;j++){
      if(j==p-1)
        sum+=x;
      else
        sum+=t.at(j);
    }
    cout<<sum<<endl;
  }


	return 0;
}



Measured memory_bytes: 3636
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REVERSE(c) reverse(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define FOR(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)

// functions
template <class T> T ceil(T a, T b) {
    return (a + b - 1) / b;
}
template <class T> T round(T a, T b) {
    return (a + b / 2) / b;
}
template <class T> T gcd(T a, T b) {
    return b ? gcd(b, a % b) : a;
}
template <class T> T lcm(T a, T b) {
    return a * b / gcd(a, b);
}
template <class T> bool amax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W;
    cin >> H >> W;
    vector<vector<char>> S(H, vector<char>(W));
    REP(i, H) {
        REP(j, W) {
            cin >> S[i][j];
        }
    }
    int dy[4] = {0, 1, 0, -1};
    int dx[4] = {-1, 0, 1, 0};
    REP(i, H) {
        REP(j, W) {
            if (S[i][j] == '.') {
                continue;
            }
            bool f = false;
            REP(k, 4) {
                int p = i + dy[k];
                int q = j + dx[k];
                if (p < 0 || p >= H || q < 0 || q >= W) {
                    continue;
                }
                f |= S[p][q] == '#';
            }
            if (!f) {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
import sys

def main():
    
    # sys.stdin = open('input155b.txt')
   
    n = int(input())
    
    a = list(map(int, input().split()))

    ans = True

    for i in a:
        if i % 2 == 1:
            continue
        if i % 2 == 0:
            if i % 3 == 0 or i % 5 == 0:
                continue
            else:
                ans = False
                
    if ans == True:
        print('APPROVED')
    else:
        print('DENIED')


if __name__ == '__main__':
    main()



Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <ctype.h>
using namespace std;
int main(){
    int N,M,C; cin >> N >> M >> C;
    int B[M];
    for (int i=0;i<M;i++) cin >> B[i];

    int ans = 0;
    for (int j=0;j<N;j++) {
        int sum_tmp=C;
        for (int i=0;i<M;i++) {
            int a_i;
            cin >> a_i;
            sum_tmp += B[i]*a_i;
        } 
        if (sum_tmp>0) ans++;
    }
    cout << ans << endl;
}


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

ll MOD = 1000000007;

ll powMod(ll x, ll k) {
  if (k == 0) return 1;
  if (k % 2 == 0)
    return powMod(x * x % MOD, k / 2);
  else
    return x * powMod(x, k - 1) % MOD;
}

int main() {
  int N;
  cin >> N;
  vector<ll> A(N), B(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
  }

  map<pair<ll, ll>, pair<int, int>> m;
  int cnt = 0;
  for (int i = 0; i < N; i++) {
    if (A[i] == 0 && B[i] == 0) {
      cnt++;
    } else if (A[i] == 0) {
      m[{0, 1}].first++;
    } else if (B[i] == 0) {
      m[{0, 1}].second++;
    } else {
      ll g = __gcd(A[i], B[i]);
      A[i] /= g, B[i] /= g;
      if (B[i] < 0) {
        A[i] *= -1;
        B[i] *= -1;
      }
      if (A[i] > 0) {
        m[{A[i], B[i]}].first++;
      } else {
        m[{B[i], -A[i]}].second++;
      }
    }
  }

  ll ans = 1;
  for (auto a : m) {
    ll tmp = 1;
    tmp += powMod(2, a.second.first) - 1 + MOD;
    tmp %= MOD;
    tmp += powMod(2, a.second.second) - 1 + MOD;
    tmp %= MOD;
    ans *= tmp;
    ans %= MOD;
  }

  cout << (ans - 1 + cnt + MOD) % MOD << endl;
}


Measured memory_bytes: 18820