akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <functional>
#include <complex>
#include <stack>
#include <tuple>
#include <array>
using namespace std;
#define rep(i,n) for (int i=0; i < (n); i++)


typedef long long int ll;
typedef double D;      // ??§?¨?????????????double???long double?????????
typedef complex<D> P;  // Point
typedef pair<P, P> L;  // Line
typedef vector<P> VP;


const int INF = (1<<30) - 1;
const D EPS = 1e-9;

#define X real()
#define Y imag()
#define LE(n,m) ((n) < (m) + EPS)
#define GE(n,m) ((n) + EPS > (m))
#define EQ(n,m) (abs((n)-(m)) < EPS)


//g++ -std=c++0x -msse4.2 -O3
//#include <bits/stdc++.h>
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cout.precision(16);
    
    int N; cin>>N;
    if(N == 0){
        cout << 1 << endl;
    }else if(N == 1){
        cout << 2 << endl;
    }else if(N == 2){
        cout << 1 << endl;
    }else{
        cout << 0 << endl;
    }
    
    
    return 0;
}

Measured memory_bytes: 1192
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <iomanip>
#include <map>
#include <queue>
#include <list>

#define REP(i, n ,N) for(ll i = (n); i < (N); i++)
//#define RREP(i, n ,N) for(ll i = (N-1); i >= (n); i--)
#define p(s) cout<<(s)<<endl
#define p2(a, b) cout<<(a)<<" "<<(b)<<endl
#define INF 1e9

using namespace std;
typedef long long  ll;

const long long MOD = 1e9+7;

int main(){
    ll a, b, k;
    cin >> a >> b >> k;
    if(a+b <= k){ p2(0, 0);}
    else if (a <= k and a+b > k){
        p2(0, b-(k-a));
    } else {
        p2(a-k, b);
    }
}

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

int main() {
    int N;
    cin >> N;
    string S;
    int num;
    int ans = 0;
    for (int i = 1; i <= N; i++){
        S = to_string(i);
        num = S.length();
        if (num%2 == 1){
            ans ++;
        }
        
    }

    cout << ans << endl;
}


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

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    int64_t ans = 1;
    for(int i = 1; i <= n; i++){
        ans *= i;
        ans %= 1000000007;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#見ずに解けていない
from collections import defaultdict
from collections import deque

graph=defaultdict(list)

n,m=map(int,input().split())
for i in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
ans=defaultdict(lambda:-1)
que=deque([1])
ans[1]=1
while len(que)>0:
    a=que.popleft()
    for b in graph[a]:
        if ans[b]==-1:
            ans[b]=a
            que.append(b)
if len(ans)!=n:
    print("No")
else:
    print("Yes")
    for b in range(2,n+1):
        print(ans[b])

Measured memory_bytes: 47580
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;

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

	int64_t s;
	s = ceil(pow(x, 1 / 5));

	int64_t a=s;
	while (1) {
		for (int64_t b = a; -1*a < b; b--) {
			if (pow(a, 5) - pow(b, 5) == x) {
				cout << a <<" "<< b << endl;

			
				return 0;
			}
		}
		a++;
	}
	
	

	


}

Measured memory_bytes: 4028
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)


const long long MOD = 1000000007;
//const long long MOD = 998244353;
const long long INF = 1LL << 60;


long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a * g / b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}




const long double PI = 3.14159265359;
const int MAX_N = 100010;




signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int a, b, c; cin >> a >> b >> c;
	int MAX = max({ a,b,c });
	MAX *= 3;
	int sum = a + b + c;
	if (MAX % 2 == sum % 2) {
		int m = max({ a,b,c });
		int ans = 0;
		ans += (m - a) / 2;
		a += (m - a) / 2 * 2;
		ans += (m - b) / 2;
		b += (m - b) / 2 * 2;
		ans += (m - c) / 2;
		c += (m - c) / 2 * 2;
		if (a != m || b != m || c != m)ans++;
		cout << ans << endl;
	}
	else {
		int m = max({ a,b,c }) + 1;
		int ans = 0;
		ans += (m - a) / 2;
		a += (m - a) / 2 * 2;
		ans += (m - b) / 2;
		b += (m - b) / 2 * 2;
		ans += (m - c) / 2;
		c += (m - c) / 2 * 2;
		if (a != m || b != m || c != m)ans++;
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> h(n);
    for(int i=0; i<n; ++i)
        cin >> h[i];

    -- h[0];
    for(int i=1; i<n; ++i){
        if(h[i] - h[i-1] < 0){
            cout << "No" << endl;
            return 0;
        }
        else if(h[i] - h[i-1] > 0){
            -- h[i];
        }
    }

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


Measured memory_bytes: 640
N, K = map(int,input().split())
L = list(map(int,input().split()))
M = []
for e in L:
    M.append(max(0,e))

S = [0]*(N+1)
T = [0]*(N+1)
for k in range(N):
    S[k+1] = L[k]+S[k]
    T[k+1] = M[k]+T[k]
ans = 0
for k in range(N-K+1):
    ans = max(ans, T[k] + max(0,S[k+K]-S[k]) + T[N]-T[k+K])
print(ans)


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

ll N;
vector<P> A;  //(活性度、番号)
vector<vector<ll>> dp(2010, vector<ll>(2010, 0));
ll res = 0;

int main(){
  cin >> N;

  ll a;
  for(ll i = 1; i <= N; i++){ cin >> a; A.push_back({a, i}); }

  sort(A.begin(), A.end());
  reverse(A.begin(), A.end());  //活性度大きい順

  for(int i = 0; i <= N; i++){  //活性度の高い順かつ合計
      ll ac = A[i].first, n = A[i].second;  //活性度とナンバー
      for(int j = 0; j <= i; j++){
        int k = i - j;
        dp[j+1][k] = max(dp[j+1][k], dp[j][k] + ac * abs(j+1-n));
        dp[j][k+1] = max(dp[j][k+1], dp[j][k] + ac * abs(N-k-n));
    }
  }

  for(int i = 0; i <= N; i++){ for(int j = 0; i+j <= N; j++) res = max(res, dp[i][j]); } 
  cout << res << endl;
  return 0;
}


  





Measured memory_bytes: 35300
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod 1000000007

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

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

ll fact(ll n){
    if(n==0)
        return 1;
    else
        return n*fact(n-1);
}

void solve(){

    string S;
    cin>>S;
    if(S[S.length()-1]=='s')
        S += "es";
    else{
        S+= 's';
    }
    cout<<S;




}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("D:\\codes\\1input.txt","r",stdin);
    //freopen("D:\\codes\\1output.txt","w",stdout);
    ll T=1;
    //cin>>T;
    for(ll t=1;t<=T;t++){
        //cout<<"Case #"<<t<<": ";
        solve();
        //cout<<"\n";
    }
}


Measured memory_bytes: 3664
import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;
import java.util.HashMap;


public class Main
{
    int h, w;
    String a[] = new String[101];
    
    public static void main(String args[])
    {
	new Main().solve();
    }
    
    void solve()
    {
	in();

	out();
    }

    void in()
    {
	Scanner sc = new Scanner(System.in);
	h = sc.nextInt();
	w = sc.nextInt();

	for(int i = 0; i < h; i++) a[i] = sc.next();
    }

    void out()
    {
	for(int i = -1; i <= h; i++) {
	    if(i == -1 || i == h) {
		String s = "";
		for(int j = 0; j < w + 2; j++) s += "#";
		out(s);
	    } else {
		String s = "#" + a[i] + "#";
		out(s);
	    }
	}
    }
    
    void out(int ans)
    {
	System.out.println(ans);
    }
    
    void out(String ans)
    {
	System.out.println(ans);
    }
}


Measured memory_bytes: 21716
#include <stdio.h>

int main()
{
    int l[3];
    for (int i = 0; i < 3; i++)
    {
        scanf("%d",&l[i]);
    }
    if((l[0] == l[1]) && (l[1] == l[2]))
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }
    
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int mex=5000001;
#define ll long long 
#define test int t;cin>>t;while(t--)
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fo(i,a,n) for(int i=a;i<n;i++)
#define rfo(i,a,b) for(int i=a;i>=b;i--)
#define bg begin()
#define en end()
#define fi first
#define se second
#define ub upper_bound
#define lb lower_bound
#define pb push_back
#define veci vector<int>
#define veclli vector<long long int> 
#define all(x) x.begin(),x.end()
#define sci(x) scanf("%d",&x);
#define scc(x) scanf("%c",&x);
#define scs(x) scanf("%s",x);
#define debug(arr,n) for(int i=0;i<n;i++) printf("%d ",arr[i]);
#define sz(x) x.size()
#define loop(x) for(auto it=x.begin();it!= x.end();it++) 

int main()
{
    ll int dp[4][105],fact[101];
    fact[0]=1;
    fo(i,1,101)
    fact[i]=fact[i-1]*i;
    fo(i,0,4)
    fo(j,0,101)
    {
        if(j>=i)
        {
            if(i==1)
        dp[i][j]=j;
        else if(i==2)
        dp[i][j]=(j*(j-1))/2;
        else dp[i][j]=(j*(j-1)*(j-2))/6;
        }
        else dp[i][j]=0;
        fo(k,1,i+1)
        dp[i][j]*=9;
    }
    fo(j,0,101)
    dp[0][j]=1;
  string s;
  cin>>s;
  int k;
  cin>>k;
  int y=k;
  int n=sz(s);
  ll int ans=0,cnt=0;
  fo(i,0,n)
  {
      
      ll int h=(s[i]-'0'-1);
      if(h>=0) cnt++;
    //cout<<n-i-1<<" "<<k<<" "<<h<<endl;
      if(h>0)
      ans=ans+h*dp[k-1][n-i-1];
      if(h>=0)
      {
      ans+=dp[k][n-i-1];
      //cout<<dp[k][n-i-1]<<" "<<dp[k-1][n-i-1]<<endl;
      
      k--;
      }
      if(k==0) break;
  }
  int fg=0;
  if(cnt==y) fg=1;
 
  cout<<ans+fg;
  
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <climits> 
int main()
{
    long L;
    std::cin >> L;
    std::cout << std::setprecision(10) << std::pow((double)L/(double)3,(double)3) << std::endl;;
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
using namespace std;
const int M=100000+5;
int n,a,b[M]={0};
int main()
{
	cin>>n;
	for(int i=0;i<n;i++){
		scanf("%d",&a);
		b[a-1]++;b[a]++;b[a+1]++;
	}
	int max=0;
	for(int i=0;i<M;i++)
		if(b[i]>max) max=b[i];
	cout<<max<<endl;
	return 0; 
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str;
 
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
 
typedef vector<int> vi; 
typedef vector<bool> vb; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
 
#define sz(x) (int)(x).size()
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define sor(x) sort(all(x))
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define endl '\n'
 
const ll MOD = 1e9+7; // 998244353;
const ll INF = 1e18;
 
ll inv (ll i) {
   ll ret = 1;
   int cur = MOD - 2;
   while (cur > 0) {
      if (cur & 1)  {
         ret *= i;
         ret = ret % MOD;
      }
      i = i * i;
      i = i % MOD;
      cur /= 2;
   }
   return ret;
}
 
int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   int s; cin >> s;
   ll ans = 0;
   for (int i = 1; s >= 3 * i; i++) {
      ll cur = 1;
      for (int j = s - 2 * i - 1; j >= s - 3 * i + 1; j--) {
         cur *= j;
         cur = cur % MOD;
      }
      for (int j = 1; j < i; j++) {
         cur *= inv(j);
         cur = cur % MOD;
      }
      ans += cur;
      ans = ans % MOD;
   }
   cout << ans;
   return 0;
}

Measured memory_bytes: 3612
using System;
using System.Linq;

public class Test
{
	public static void Main()
	{
		var p = Console.ReadLine().Split().Select(i=>int.Parse(i)).ToArray();
		var q = Console.ReadLine().Split().Select(i=>int.Parse(i)).ToArray();
		Console.WriteLine((p[0] - q[0]) * (p[1] - q[1]));
	}
}

Measured memory_bytes: 13268
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    if(n % 10 == 3){
        cout << "bon" << endl;
    }else if(n % 10 == 0 || n % 10 == 1 || n % 10 == 6 || n % 10 == 8){
        cout << "pon" << endl;
    }else{
        cout << "hon" << endl;
    }

    return 0;
}

Measured memory_bytes: 3596
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>

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 vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EACH(t,i,c) for(t::iretator i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

const double EPS = 1e-10;

int main() {
	int N, A, B, C, X, i, n, nn, j=0;
	int numbers[100];

	cin >> N >> A >> B >> C >> X;

	while(N || A || B || C || X) {

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

	j = N;
	n = nn = X;

	for(i = 0; i <= 10000; i++) {
		if(n == numbers[N-j]) {
			j--;
		}
	
		if(j == 0) {
			goto success;
		}

		n = (A*nn+B)%C;

		nn = n;
	}
	
	cout << "-1" << endl;
	goto next;

success:
	cout << i << endl;
	goto next;
	
next:
	cin >> N >> A >> B >> C >> X;
	}
}

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

#define __STDC_FORMAT_MACROS
#define p64 PRId64

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR (i, 0, n)
#define ALL(f, x, ...)                                                         \
    ([&] (decltype ((x)) ALL) {                                                \
        return (f) (begin (ALL), end (ALL), ##__VA_ARGS__);                    \
    }) (x)

using namespace std;
using ll = int64_t;

int main() {
    int A, B;
    cin >> A >> B;
    cout << ((A + B) % 2 == 0 ? to_string ((A + B) / 2) : "IMPOSSIBLE") << endl;
    return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main(){
    ll n; cin>>n;
    map<ll,ll> e;
    ll res1=0, res2=0;
    rep(i,n){
        ll a; cin>>a;
        e[a]++;
        if(e[a]==2){
            if(a>res1){
                res2=res1;
                res1=a;
            }else if(a>res2){
                res2=a;
            }
            e[a]=0;
        }
    }
    cout<<res1*res2<<endl;
    return 0;
}

Measured memory_bytes: 6528
# ABC117C - Streamline
def main():
    n, m = map(int, input().split())
    lst = sorted(set(map(int, input().split())))
    dis = []
    for i, j in zip(lst, lst[1:]):
        dis += [j - i]
    print(sum(sorted(dis, reverse=True)[n - 1 :]))


if __name__ == "__main__":
    main()


Measured memory_bytes: 18960
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

inf = int(1e10)
mod = int(1e9 + 7)


def solve(N):
    c1 = pow(10, N, mod)
    c2 = (2 * pow(9, N, mod)) % mod
    c3 = pow(8, N, mod)
    ans = (c1 - c2) % mod
    ans = (ans + c3) % mod
    return ans

def main():
    from builtins import int, map
    N = int(input())

    ans = -1
    if N == 1:
        ans = 0
    elif N == 2:
        ans = 2
    else:
        ans = solve(N)
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 65400
{-# LANGUAGE OverloadedStrings #-}
module Main where

import           Data.List
import           Control.Monad
import           Debug.Trace
import qualified Data.ByteString.Char8         as BC
import           Data.Maybe                     ( fromJust )
import qualified Data.Set                      as S
import qualified Data.IntMap.Strict            as IM
import qualified Data.IntMap.Lazy            as IML
import qualified Data.Map.Strict               as M
import qualified Data.Map.Lazy               as ML
import           Data.Char
import qualified Data.Array.IArray as A
import Data.Bits

modN = 1000000007


readTuple2 :: IO (Int, Int)
readTuple2 = do
    [a, b] <- map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine
    return (a, b)

readTuple3 :: IO (Int, Int, Int)
readTuple3 = do
    [a, b, c] <- map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine
    return (a, b, c)

readInt :: IO Int
readInt = fst . fromJust . BC.readInt <$> BC.getLine

readInts :: IO [Int]
readInts = map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine

split :: (a -> Bool) -> [a] -> [[a]]
split f [] = []
split f as =
    let (fo, la) = span f as
        las      = case la of
            [] -> []
            xs -> split f $ tail xs
    in  case fo of
            [] -> las
            xs -> xs : las

pow :: Int -> Int -> Int -> Int
pow base 1 modNum = base `mod` modNum
pow base time modNum
    | odd time = let 
        a = pow base (time `div` 2) modNum `mod` modNum
        in
        a * a * base `mod` modNum
    | otherwise = let
        a = pow base (time `div` 2) modNum `mod` modNum
        in
        a * a `mod` modNum

solve :: Int -> [(Int, Int, Int)] -> Int
solve n acts = let
    actMap = IM.fromList $ zip [1..] acts
    getIJ :: Int -> Int -> Int
    getIJ 0 _ = 0
    getIJ i j = let
        (a, b, c) = actMap IM.! i
        actL = [a, b, c]
        in maximum $ do
            prevActs <- [1,2,3]
            guard $ j /= prevActs
            let prevNum = dp ML.! ((i - 1), prevActs)
            let currentNum = actL !! (j - 1)
            pure $ prevNum + currentNum
        
    dp = ML.fromList [((i, j), getIJ i j)| i <- [0..n], j <- [1..3]]
    in maximum $ do
        j <- [1,2,3]
        pure $ dp ML.! (n, j)


main = do
    n <- readInt
    acts <- replicateM n readTuple3
    print $ solve n acts







Measured memory_bytes: 156028
s = input()
t = input()

t1 = sorted(t,reverse=True)
s1 = sorted(s)

hantei = 0
count = 0

if len(s1) < len(t1):
    for i in range(len(s1)):
        count += 1
        if t1[i] > s1[i]:
            hantei = 1
            break
        elif t1[i] < s1[i]:
            break
        elif count == len(s1):
            hantei = 1
            break

else :
     for i in range(len(t1)):
        if t1[i] > s1[i]:
            hantei = 1
            break
        elif t1[i] < s1[i]:
            break

if hantei == 1:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define ll long long
#define endl '\n'
using namespace std;
unsigned gcd(unsigned a, unsigned b) {
    while (1) {
        if (a < b) swap(a, b);
        if (!b) break;
        a %= b;
    }
    return a;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, k;
    cin >> n >> k;
    ll a[100000];
    rep(i, n) { cin >> a[i]; }
    ll g = a[0];
    ll m = a[0];
    for (int i = 1; i < n; i++) {
        g = gcd(g, a[i]);
        m = max(m, a[i]);
    }
    if (k <= m && k % g == 0) {
        puts("POSSIBLE");
    } else {
        puts("IMPOSSIBLE");
    }
    return 0;
}

Measured memory_bytes: 1024
"use strict";
function Main(input) {
    let lines = input.split("\n");
    let lines1 = lines.shift().split(/\s/).map((v) => v - 0);
    let N = lines1[0];
    let M = lines1[1];
    let a = lines[0].split(/\s/).map((v) => v - 0);

    const u = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6];
    let v = [];
    a.sort((a, b) => b - a);
    for (let m = 0; m < M; m++) {
        v[m] = u[a[m]];
    }
    var ans = [""];
    for (let n = 1; n <= N; n++) {
        for (let m = 0; m < M; m++) {
            const t = n - v[m];
            if (t >= 0 && ans[t] !== undefined) {
                if (ans[n] === undefined) ans[n] = "";
                const l = ans[n].length;
                if (l <= ans[t].length) {
                    ans[n] = ans[t] + a[m];
                }
            }
        }
    }
    ans = ans[N].split("");
    ans.sort((a, b) => b - a);
    console.log(ans.join(""));
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 8392
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

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

const ll INF = 1LL << 50;

struct UnionFind {
  vll par;
  vll wcnt;
  vll bcnt;
  ll cnt;
  UnionFind(ll N, vector<string>& mp) : par(N), wcnt(N, 0), bcnt(N, 0), cnt(N) {
    for (ll i = 0; i < N; i++) {
      par[i] = i;
      ll w = (ll)mp[0].size();
      if (mp[i / w][i % w] == '.')
        wcnt[i] = 1;
      else
        bcnt[i] = 1;
    }
  }

  ll find(ll x) { return par[x] == x ? x : par[x] = find(par[x]); }

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

  ll get_wcnt(ll x) { return wcnt[find(x)]; }
  ll get_bcnt(ll x) { return bcnt[find(x)]; }

  void unite(ll x, ll y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    ll sizex = wcnt[x] + bcnt[x];
    ll sizey = wcnt[y] + bcnt[y];
    if (sizex < sizey) swap(x, y);
    par[y] = x;
    wcnt[x] += wcnt[y];
    bcnt[x] += bcnt[y];
    cnt--;
  }

  ll count() const { return cnt; }
};

int main() {
  ll n;
  cin >> n;
  vll cum(n + 1, 0);
  rep(i, n) {
    ll a;
    cin >> a;
    cum[i + 1] = cum[i] + a;
  }
  ll ans = LONG_LONG_MAX;
  rep(i, n - 1) {
    ll l = cum[i + 1];
    ll r = cum[n] - cum[i + 1];
    chmin(ans, abs(l - r));
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0;
#define ll long long

int n, m, x, y, z, vis[100001], val[100001];
vector <pair <int, int> > v[100001];
bool can;

void dfs(int node){
    if(vis[node]) return;
    vis[node] = 1;
    for(auto i : v[node]){
        if(val[i.first] == -1) val[i.first] = val[node]+i.second;
        else if(val[i.first] != val[node]+i.second) can = 0;
        dfs(i.first);
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(val, -1, sizeof val);
    cin >> n >> m;
    while(m-- && cin >> x >> y >> z){
        v[x].push_back(make_pair(y, z));
        v[y].push_back(make_pair(x, -z));
    }
    for(int i = 1 ; i <= n ; i++) if(vis[i] == 0){
        can = 1;
        val[i] = 0;
        dfs(i);
        if(!can) finish("No");
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 13440
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>
#include <bitset>
#include <cstdint>

using namespace std;
using lli = long long int;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

struct UnionFind {
  vector<int> c, s;
  UnionFind(size_t n) : c(n), s(n, 1) { iota(begin(c), end(c), 0); }
  int root(int i) { return c[i] == i ? i : (c[i] = root(c[i])); }
  bool same(int i, int j) { return root(i) == root(j); }
  void unite(int i, int j) {
    i = root(i); j = root(j);
    if (i != j) {
      if (s[i] > s[j]) { c[j] = i; s[i] += s[j]; }
      else { c[i] = j; s[j] += s[i]; }
    }
  }
  int size(int i) { return s[root(i)]; }
};

i64 n, m;
vector<i64> x, y, z;
int main() {
  cin >> n >> m;
  init_n(x, m);
  init_n(y, m);
  init_n(z, m);
  for (i64 i = 0; i < m; ++i) {
    cin >> x[i] >> y[i] >> z[i];
  }

  UnionFind uf(n + 1);
  for (i64 i = 0; i < m; ++i) {
    uf.unite(x[i], y[i]);
  }

  set<i64> st;
  for (i64 i = 1; i <= n; ++i) {
    st.insert(uf.root(i));
  }

  cout << st.size() << '\n';
  return 0;
}


Measured memory_bytes: 8064
//コンパイラ最適化用
#pragma GCC optimize("Ofast")
#define _GLIBCXX_DEBUG
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<chrono>//実行時間計測
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm,accumulate
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//順序保持しないmap
#include<unordered_set>//順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;
typedef pair<ll, ld> pld;
typedef pair<pii, int> ppiii;
typedef pair<pii, ll> ppiill;
typedef pair<pll, ll> ppllll;
typedef pair<pli, int> pplii;
typedef map<int, int> mii;
typedef deque<ll> dll;
typedef queue<ll> qll;
typedef priority_queue<ll> pqll;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqrll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<int>> vvint;
typedef vector<vector<pll>> vvpll;

//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define cin(x) cin >> x

signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    //入力
    vvll c(3,vll(3));
    REP(i,3){
      REP(j,3){
        cin >> c[i][j];
      }
    }

    //本文
    bool check = true;
    if(c[0][1]-c[0][0]!=c[1][1]-c[1][0]||c[1][1]-c[1][0]!=c[2][1]-c[2][0]) check = false;
    if(c[0][2]-c[0][1]!=c[1][2]-c[1][1]||c[1][2]-c[1][1]!=c[2][2]-c[2][1]) check = false;
    if(c[1][0]-c[0][0]!=c[1][1]-c[0][1]||c[1][1]-c[0][1]!=c[1][2]-c[0][2]) check = false;
    if(c[2][0]-c[1][0]!=c[2][1]-c[1][1]||c[2][1]-c[1][1]!=c[2][2]-c[1][2]) check = false;
    //出力
    if(check) cout << "Yes" << endl;
    else cout << "No" << endl;
    //REP(i,N) cout << ans.at(i) <<endl;
  return 0;
}

Measured memory_bytes: 3644
n = int(input())
ten = [list(map(int, input().split())) for i in range(n)]

for i in ten:
    x = i[0]
    y = i[1]
    i[0] = x-y
    i[1] = x+y

xmax = i[0]
xmin = i[0]
ymax = i[1]
ymin = i[1]
for i in ten:
    xmax = max(xmax,i[0])
    xmin = min(xmin,i[0])
    ymax = max(ymax,i[1])
    ymin = min(ymin,i[1])

print(max(xmax-xmin,ymax-ymin))

Measured memory_bytes: 102480
import java.util.*
fun toS(x: Int): String {
    val s = x.toString()
    if (s.length == 1) {
        return "00" + s
    } else if (s.length == 2) {
        return "0" + s
    }
    return s
}

class Shop(name: String, point: Int, number: Int) {
    val dict = name + "               " + toS(100-point)
    val number = number
}

fun main(args: Array<String>){
	val cin = Scanner(System.`in`)
    val n = cin.nextInt()
    val a: MutableList<Shop> = mutableListOf()
    for (i in 1..n) {
        a.add(Shop(cin.next(), cin.nextInt(), i))
    } 
    val a_s = a.sortedBy { it.dict }
    for (i in 0..n-1) {
        println(a_s[i].number)
    }
}

Measured memory_bytes: 34156
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Abc
{
    class QuestionB
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数配列の入力
            var num_XY = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();

            var X = num_XY[0]; //頭数
            var Y = num_XY[1]; //足数

            if (Y % 2 == 0) //足数が偶数のときのみ判定
            {
                //カメの数
                var Kame = (Y - 2 * X) / 2;

                //ツルの数
                var Tsuru = (4 * X - Y) / 2;

                if (Kame >= 0 & Tsuru >= 0)
                {
                    Console.WriteLine("Yes");
                }
                else
                {
                    Console.WriteLine("No");
                }
            }
            else Console.WriteLine("No");
            

            
            Console.Out.Flush();
        }
    }
}


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

using namespace std;

const int N = 1e5 + 2;

int n, d[N], u[N], a[N], b[N];
vector <int> g[N], vec;

void dfs(int v, int pr = 0){
      for(int to : g[v]){
            if(to == pr) continue;
            d[to] = d[v] + 1;
            dfs(to, v);
      }
}

bool mark(int v, int x, int pr = 0){
      if(v == x){
            u[v] = 1;
            vec.push_back(x);
            return true;
      }

      for(int to : g[v]){
            if(to == pr) continue;
            if(mark(to, x, v)){
                  u[v] = 1;
                  vec.push_back(v);
                  return true;
            }
      }

      return false;
}

bool fun(){
      for(int i = 1; i <= n; i ++){
            if(a[i] == b[i]) continue;
            if(a[i] > b[i]) return false;
            else return true;
      }
      return true;
}

int main(){
      cin >> n;

      for(int i = 1; i < n; i ++){
            int x, y;
            cin >> x >> y;
            g[x].push_back(y);
            g[y].push_back(x);
      }

      dfs(1);

      int ind = 1;

      for(int i = 1; i <= n; i ++){
            if(d[ind] < d[i])
                  ind = i;
      }

      d[ind] = 0;
      int vr = ind;
      dfs(ind);

      ind = 1;

      for(int i = 1; i <= n; i ++){
            if(d[ind] < d[i])
                  ind = i;
      }

      mark(vr, ind);

      int cn = vec.size();

      for(int i = 1; i <= n; i ++){
            if(u[i]){
                  for(int to : g[i]){
                        if(u[to]) continue;
                        cn ++;
                  }
            }
      }

      if(cn != n){
            puts("-1");
            return 0;
      }

      int pos = 0, val = 0;

      for(int i = 0; i < vec.size(); i ++){
            int cnt = 0;
            int v = vec[i];
            for(int to : g[v]){
                  if(u[to]) continue;
                  cnt ++;
            }
            int now = ++ val;
            while(cnt > 0){
                  cnt --;
                  a[++ pos] = ++ val;
            }
            a[++ pos] = now;
      }

      reverse(vec.begin(), vec.end());

      pos = val = 0;

      for(int i = 0; i < vec.size(); i ++){
            int cnt = 0;
            int v = vec[i];
            for(int to : g[v]){
                  if(u[to]) continue;
                  cnt ++;
            }
            int now = ++ val;
            while(cnt > 0){
                  cnt --;
                  b[++ pos] = ++ val;
            }
            b[++ pos] = now;
      }

      if(fun()){
            for(int i = 1; i <= n; i ++)
                  cout << a[i] << " ";
      } else{
            for(int i = 1; i <= n; i ++)
                  cout << b[i] << " ";
      }
}


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

int g[10][10];

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

int n,m;cin>>n>>m;
for(int i=0;i<m;i++){
  int a,b;cin>>a>>b;a--,b--;
  g[a][b]=1;g[b][a]=1;
}
vector<int> v(n);
for(int i=0;i<n;i++)v[i]=i;
int ans=0;
do{
  bool ok=true;
  if(v[0]!=0)continue;
  for(int i=0;i<n-1;i++){
    int a = v[i];int b = v[i+1];
    if(!g[a][b])ok=false;
  }
  if(ok)ans++;
} while(next_permutation(v.begin(), v.end()));
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3600
S=list(input())
F=int(''.join(S[0:2]))
B=int(''.join(S[2:4]))
if 0<F<13 and 0<B<13:
  ans='AMBIGUOUS'
elif F>12 and B>12:
  ans='NA'
elif F>12 and 0<B<13:
  ans='YYMM'
elif B>12 and 0<F<13:
  ans='MMYY'
elif F==0:
  if not 0<B<13:
    ans='NA'
  else:
    ans='YYMM'
elif B==0:
  if not 0<F<13:
    ans='NA'
  else:
    ans='MMYY'
print(ans)
  

Measured memory_bytes: 3064
import Data.List(isInfixOf)
main = do
  s <- getLine
  p <- getLine
  putStrLn $ if solve2 (s++s) p then "Yes"
             else "No"

solve :: String -> String -> Bool
solve a@(x:xs) p
  | slice 0 (length p) a == p = True
  | length(a) <= length(p) = False
  | otherwise = solve xs p           
  where slice ::  Int -> Int -> String -> String
        slice m n s = (take (n-m) . drop m) $ s

solve2 :: String -> String -> Bool
solve2 s p = p `isInfixOf` s

Measured memory_bytes: 3520
#include<iostream>
#define ll long long

int main (){
ll n;
std::cin >> n;
ll a[n],store[1000000];
for(ll i=0;i<1000000;i++) store[i]=0;
ll t=0;
for(ll i=1;i<=n;i++) {
	std::cin >> a[i];
	store[a[i]]++;
	t+=a[i];
}	
ll q;
std::cin >> q;
while(q--){
ll b,c;
std::cin >> b >> c;	
t-=(store[b]*b);
t+=(store[b]*c);	
store[c]+=store[b]; // updating c frequency
store[b]=0;//updating b frequency
std::cout << t << std::endl;
}
 return 0;
}


Measured memory_bytes: 12160
N,K=map(int,input().split())
H=list(map(int,input().split()))
dp=[0 for i in range(N)]
def calcmin(n,d):#インデックスがnのノードまでいくための最小コスト（最大移動距離はd）
  p=dp[n-d]+abs(H[n-d]-H[n])
  for q in range(d):
    if p>dp[n-(d-q)]+abs(H[n-(d-q)]-H[n]):
      p=dp[n-(d-q)]+abs(H[n-(d-q)]-H[n])
  return p
for i in range(min(K,N)):
  dp[i]=calcmin(i,i)
for i in range(K,N):
  dp[i]=calcmin(i,K)
print(dp[N-1]) 

Measured memory_bytes: 56544
/*Unlucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e6;

int n,a,b,c,d;
char str[N+7];

int main(){
	scanf("%d%d%d%d%d%s",&n,&a,&b,&c,&d,str+1);
	for(int i=a+1;i<=c;i++)
		if(str[i]==str[i-1] && str[i]=='#')
			printf("No\n"),exit(0);
	for(int i=b+1;i<=d;i++)
		if(str[i]==str[i-1] && str[i]=='#')
			printf("No\n"),exit(0);
	if(c<d) printf("Yes\n"),exit(0);
	for(int i=b;i<=d;i++)
		if(str[i-1]==str[i] && str[i]==str[i+1] && str[i]=='.')
			printf("Yes\n"),exit(0);
	printf("No\n");
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define MOD 1000000007
using namespace std;
const int MAXN = 100005;
long long s[MAXN],a,b;
int n,limita[MAXN],d[MAXN],suf[MAXN],sum[MAXN],f[MAXN];
int main()
{
	scanf("%d%lld%lld",&n,&a,&b);
	if(a<b)swap(a,b);
	for(int i=1;i<=n;++i)
		scanf("%lld",s+i);
	int p1=0,p2=0;
	s[0]=-max(a,b);
	for(int i=1;i<=n;++i)
		if(i>2)if(s[i]-s[i-2]<b){puts("0");return 0;}
	f[0]=sum[0]=1;
	s[n+1]=(long long)2e18+100;
	for(int i=1;i<=n+1;++i){
		while(s[i]-s[p1+1]>=a && p1+1<i)++p1;
		long long o=i>=2?s[i-1]-s[i-2]:max(a,b);
		if(o<b)p2=i-1;
		if(p1>=p2-1)f[i]=(sum[p1]-(p2>=2?sum[p2-2]:0)+MOD)%MOD;
		else f[i]=0;
		sum[i]=(sum[i-1]+f[i])%MOD;
	}
	cout<<f[n+1]<<endl;
	return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define P pair<int,int>
#define PI 3.141592653589793
const int INF = 1001001001;
const ll MX = 1e18;
const int mod = 1000000007;

int main() {
	ll l, r;
	cin >> l >> r;
	if (r - l + 1 >= 2019) {
		cout << 0 << endl;
		return 0;
	}
	ll R = r % 2019;
	ll L = l % 2019;
	if (R<L) {
		cout << 0 << endl;
		return 0;
	}
	ll ans = 2019;
	for (ll i = L; i <= R; i++) {
		for (ll j = i+1; j <= R; j++) {
			ll a = (i * j) % 2019;
			ans = min(ans, a);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3580
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int n;
  long long t;
  scanf("%d %lld", &n, &t);
  vector<pair<int, int>> val;
  vector<int> add;
  for (int i = 0; i < n; ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    ++a, ++b;
    if (a == 1)
      add.push_back(b);
    else
      val.emplace_back(a, b);
  }
  sort(val.begin(), val.end(), [](pair<int, int> le, pair<int, int> ri) {
    long long lef = 1LL * le.second * ri.first + ri.second;
    long long rig = 1LL * ri.second * le.first + le.second;
    return lef < rig;
  });
  ++t;
  vector<long long> dp;
  dp.push_back(1);
  for (auto it : val) {
    vector<long long> ndp = dp;
    ndp.push_back(t+1);
    for (int i = 0; i < (int)dp.size(); ++i) {
      ndp[i+1] = min(it.first * dp[i] + it.second, ndp[i+1]);
    }
    while (!ndp.empty() && ndp.back() > t)
      ndp.pop_back();
    dp.swap(ndp);
  }
  sort(add.begin(), add.end());
  vector<int> tot;
  int now = 0;
  tot.push_back(now);
  for (int x : add) {
    now += x;
    if (now > t) break;
    tot.push_back(now);
  }
  int ans = (int)dp.size()-1;
  for (int i = 0; i < (int)dp.size(); ++i) {
    int sisa = t - dp[i];
    int id = upper_bound(tot.begin(), tot.end(), sisa) - tot.begin()-1;
    ans = max(ans, i+id);
  }
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 2548
def main():
    mod = 998244353
    s, k = input().split()
    k, n, one, cnt, z, zero_list = int(k), len(s), s.count("1")+1, 0, 0, []
    for i in range(n):
        if s[i] == "0":
            zero_list.append(cnt)
            cnt = 0
        else:
            cnt += 1
    mm = min(one-1, k)

    dp = [[0]*(mm+1) for _ in [0]*one]
    dp[0][0] = 1

    for i in zero_list:
        dp2 = [[0]*(mm+1) for _ in [0]*one]
        for j in range(one):
            for l in range(max(z+i-j, 0), one-j):
                ml = max(l-i, 0)
                for p in range(min(j, mm-ml)+1):
                    dp2[j+l][p+ml] = (dp2[j+l][p+ml]+dp[j][p]) % mod
        z += i
        dp = dp2
    print(sum([sum(i) for i in dp]) % mod)


main()

Measured memory_bytes: 88224
N, M = map(int, input().split())
road = [[int(i) for i in input().split()] for j in range(M)]
road_s = [i[0] for i in road]
road_g = [i[1] for i in road]

for i in range(1,N+1):
    print(road_s.count(i) + road_g.count(i))


Measured memory_bytes: 2940
/*
Code Author: ADITYA SHETH (^_^)
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
#define t1(x)             cerr<<#x<<"="<<x<<endl
#define t2(x, y)          cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define t3(x, y, z)       cerr<<#x<<"=" <<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define t4(a,b,c,d)       cerr<<#a<<"="<<a<<" "<<#b<<"="<<b<<" "<<#c<<"="<<c<<" "<<#d<<"="<<d<<endl
#define t5(a,b,c,d,e)     cerr<<#a<<"="<<a<<" "<<#b<<"="<<b<<" "<<#c<<"="<<c<<" "<<#d<<"="<<d<<" "<<#e<<"="<<e<<endl
#define t6(a,b,c,d,e,f)   cerr<<#a<<"="<<a<<" "<<#b<<"="<<b<<" "<<#c<<"="<<c<<" "<<#d<<"="<<d<<" "<<#e<<"="<<e<<" "<<#f<<"="<<f<<endl
#define GET_MACRO(_1,_2,_3,_4,_5,_6,NAME,...) NAME
#define t(...) GET_MACRO(__VA_ARGS__,t6,t5, t4, t3, t2, t1)(__VA_ARGS__)
//freopen("output.txt","w",stdout);
//freopen("input.txt","r",stdin);
/*-------------------------------------------------------------------------------------------------------------------------------------*/
#define MOD 1000000007
#define endl "\n" 
//#define int long long // remove when constraints are tight.
/*-------------------------------------------------------------------------------------------------------------------------------------*/

int string_to_int(string ss)
{
	int ans=0;

	for(int i=0;i<ss.length();i++)
	{
		ans=ans*26+(ss[i]-'a'+1);
	}
	//t(ss,ans);
	return ans;
}
const int N=2e5+100;
const int K=28*28;
int dp[N][K];
string s;
int n;
int rec(int ind,int prev)
{
	//t(ind,prev);
	if(ind>=n)
	{
		return 0;
	}
	int &ans=dp[ind][prev];
	if(ans>=0)
	{
		return ans;
	}
	//t(ind,prev);
	ans=0;
	string cur;
	cur+=s[ind];
	///t(cur);
	//t(ind,prev);
	if(string_to_int(cur)!=prev)
	{
		ans=max(ans,1+rec(ind+1,string_to_int(cur)));
		//t(ind,prev);
	}
	//t(ind,prev);
	if(ind==n-1)
	{
		return ans;
	}
	//t(ind,prev);
	cur+=s[ind+1];
	if(string_to_int(cur)!=prev)
	{
		ans=max(ans,1+rec(ind+2,string_to_int(cur)));
	}
	//t(ind,prev);
	return ans;
}
int32_t main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	memset(dp,-1,sizeof(dp));
	cin>>s;
	n=s.length();
	cout<<rec(0,27*27);
}


Measured memory_bytes: 664468
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <tuple>

#include <set>
//#include <unordered_map>
#include <stack>

using namespace std;

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




int main() {

vector<pair<int, int> > pairs;
int N;
	cin >> N;

	rep(i, N)
	{
		long long x, l;
		cin >> x >> l;
		pairs.push_back(make_pair(x + l, x - l));
	}
	sort(pairs.begin(), pairs.end());

	int now = pairs[0].first;
	int ans = 1;

	rep(i, N - 1) {
		if (pairs[i + 1].second >= now) {
			now = pairs[i + 1].first;
			ans++;
		}
	}


	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
ll h, w, dp[1005][1005];
char grid[1005][1005];
ll const mod = 1e9+7;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> h >> w;
	for (ll i = 0; i < h; i++){
		string s;
		cin >> s;
		for (ll j = 0; j < s.length(); j++){
			grid[i][j] = s[j];
		}
	}
	dp[1][1] = 1;
	for (ll i= 1; i <= h; i++){
		for (ll j = 1; j <= w; j++){
			if (grid[i-1][j-1] == '#' || (i == 1 && j == 1))continue;
			dp[i][j] = (dp[i-1][j]%mod + dp[i][j-1]%mod)%mod;
		}
	}
	cout << dp[h][w]%mod;
}


Measured memory_bytes: 9088
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int main(){
    int n;

    while(cin>>n,n){
        int id;
        ll p,q;
        vector<pair<int,ll>> v;

        for(int i=0;i<n;i++){
            cin >> id >> p >> q;

            for( auto &t:v ){
                if( t.first==id ){
                    t.second += p*q;
                    id=-1;
                    break;
                }
            }

            if(id!=-1){
                v.push_back(make_pair(id,p*q));
            }
        }

        bool flag=false;
        for( auto t:v ){
            if( t.second>=1000000 ){
                cout<<t.first<<endl;
                flag=true;
            }
        }

        if(!flag) cout<<"NA"<<endl;
    }

    return 0;
}

Measured memory_bytes: 1240
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();

        if(a<b){
            if(b<c){
                System.out.printf("%d %d %d\n",a,b,c);
            }else{
                if(a>c){
                    System.out.printf("%d %d %d\n",c,a,b);
                }else{
                    System.out.printf("%d %d %d\n",a,c,b);
                }
            }
        }
        else{
            if(a<c){
                System.out.printf("%d %d %d\n",b,a,c);
            }else{
                if(b>c){
                    System.out.printf("%d %d %d\n",c,b,a);
                }else{
                    System.out.printf("%d %d %d\n",b,c,a);
                }
            }
        }
    }

}


Measured memory_bytes: 26340