akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long int
#define mp make_pair
#define pb push_back
#define ff first 
#define ss second
#define mod 1000000007
#define lim 100005
#define nfs_mw ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int main()
{
	int i,j,n,k,t,a[lim],b[lim],c[lim],dp[lim][3] = {};
	cin>>n;
	for(i=1; i<=n; i++) cin>>a[i]>>b[i]>>c[i];
	for(i=1; i<=n; i++){
		dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i];
		dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b[i];
		dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c[i];
	}
	cout<<max({dp[n][0], dp[n][1], dp[n][2]});
}

Measured memory_bytes: 2560
//21
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

const int maxn = 100001;

int n, s;
int x[maxn];
long long p[maxn];

int main() {
	scanf("%d%d", &n, &s);
	for (int i = 1; i <= n; i++) {
		scanf("%d %lld", &x[i], &p[i]);
	}
	long long ans = 0;
	int l = 1;
	int r = n;
	int last = 0;
	while (x[l] < s && x[r] > s) {
		if (p[l] >= p[r]) {
			if (last) ans += abs(x[r] - x[last]);
			last = r;
			p[l] += p[r--];
		}
		else {
			if (last) ans += abs(x[l] - x[last]);
			last = l;
			p[r] += p[l++];
		}
	}
	if (x[l] > s) {
		if (last) ans += abs(x[r] - x[last]);
		ans += x[r] - s;
	}
	if (x[r] < s) {
		if (last) ans += abs(x[l] - x[last]);
		ans += s - x[l];
	}
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 1280
object Main {

    def main(args: Array[String]): Unit = {
        val sc = new java.util.Scanner(System.in)

        grade(sc)
    }

    def grade(scanner: java.util.Scanner): Unit = {
        val m, f, r = scanner.nextInt

        if( m != -1 || f != -1 || r != -1 ) {
            (m, f, r) match {
                case (-1, _, _) => println("F")
                case (_, -1, _) => println("F")
                case _ => {
                    m+f match {
                        case a if a >= 80 => println("A")
                        case b if b >= 65 => println("B")
                        case c if c >= 50 => println("C")
                        case d if d >= 30 => {
                            println(if( r >= 50 ) "C" else "D")
                        }
                        case _ => println("F")
                    }
                }
            }

            grade(scanner)
        }
    }
}



Measured memory_bytes: 44976
#include <ctime>
#include <iomanip>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <list>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
using namespace std;

#define int long long
#define INF 1e18
#define EPS 1e-9
#define NIL -1
#define N 100

signed main() {
    int d, g, p[11], c[11];
    cin >> d >> g;
    for(int i = 0;i < d; i++) {
        cin >> p[i] >> c[i];
    }

    int ans = 1e9;
    for(int mask = 0; mask < (1 << d); mask++) {
        int s = 0, num = 0, rest_max = -1;
        for(int i = 0; i < d; i++) {
            if(mask >> i & 1) {
                s += 100 * (i + 1) * p[i] + c[i];
                num += p[i];
            } else {
                rest_max = i;
            }
        }
        if(s < g) {
            int s1 = 100 * (rest_max + 1);
            int need = (g - s + s1 - 1) / s1;
            if(need >= p[rest_max]) {
                continue;
            }
            num += need;
        }
        ans = min(ans, num);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
n=int(input())
l=[tuple(map(int,input().split())) for i in range(n)]
k=[[None,None,None] for i in range(n)]
k[0][0]=l[0][0]
k[0][1]=l[0][1]
k[0][2]=l[0][2]

for i,(a,b,c) in enumerate(l[1:]):
    k[i+1][0]=max(k[i][1],k[i][2])+a
    k[i+1][1]=max(k[i][0],k[i][2])+b
    k[i+1][2]=max(k[i][1],k[i][0])+c
print(max(k[n-1][0],k[n-1][1],k[n-1][2]))

Measured memory_bytes: 41004
s = list(input())
k = int(input())

znext = ord('z') + 1
for i in range(len(s)):
    if k == 0:
        break
    if s[i] == 'a':
        continue
    if k >= znext - ord(s[i]):
        k -= znext - ord(s[i])
        s[i] = 'a'
s[-1] = chr(ord(s[-1]) + k % 26)
print(''.join(s))


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

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

	int data[] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };

	k--;
	cout << data[k] << endl;

	return 0;
}


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

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] t = new int[n + 1];
		for(int i = 1; i <= n; i++) t[i] = sc.nextInt();
		int m = sc.nextInt();
		int[] p = new int[m + 1];
		int[] x = new int[m + 1];
		int time;
		for(int i = 1; i <= m; i++) {
			p[i] = sc.nextInt();
			x[i] = sc.nextInt();
		}
		for(int i = 1; i <= m; i++) {
			time = 0;
			for(int j = 1; j <= n; j++) {
				if(j == p[i]) time += x[i];
				else time += t[j];
			}
			System.out.println(time);
		}
	}
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define lli long long int
#define ulli unsigned long long int
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pf pop_front()
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define loopl(i,a,b) for(lli i=a;i<b;i++) 
#define loop(i,a,b) for(int i=a;i<b;i++)
#define mod 1000000007
#define inf 100000000000000000
#define lld long double
#define pll pair<long long int,long long int>
#define vll vector<lli>
#define eps 0.000001
#define endl '\n'
#define mo 998244353
 
using namespace std ;
 
#define MAXN 200005 

typedef tree<lli,null_type,less<lli>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;

lld dp[3001][3001];

int main()
{

    lli n;
    cin>>n;

    lld p[n+1];

    loopl(i,1,n+1) cin>>p[i];

    dp[0][0] = 1;

    loopl(i,1,n+1)
    {
        loopl(j,0,n+1)
        {
            if(j>i)
                break;

            dp[i][j] = dp[i-1][j]*(1-p[i]) ;
            if(j>=1) dp[i][j] +=  dp[i-1][j-1]*p[i];
        }
    }


    lld ans=0;

    loopl(i,n/2 + 1 , n+1)
    ans += dp[n][i];

    cout<<fixed<<setprecision(12)<<ans<<endl;


}

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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    int A[N], B[N];
    rep(i, N) cin >> A[i] >> B[i];
    sort(A, A+N);
    sort(B, B+N);
    if(N % 2 == 1){
        cout << B[(N-1) - (N-1)/2] - A[(N-1)/2] + 1 << endl;
    }
    else{
        int k = (N-2)/2;
        ll ma = A[k] + A[k+1];
        ll mb = B[k] + B[k+1];
        cout << mb-ma+1 << endl;
    }
    return 0;
}

Measured memory_bytes: 5204
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <string.h>
#include <vector>
#include <set>
#include <map>
#include <queue>

using namespace std;

#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define y0 isdnfviu
#define y1 asinhiv
#define fst first
#define snd second

int main()
{
	string s,t;
    cin>>s>>t;
    int c=0;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]!=t[i])
        c++;
    }
    cout<<c;
}


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

signed main(){
    int n , num , ans = 0;
    string s;
    bool c[11][11][11] = {};
    
    cin >> n;
    cin >> s;
    for(int i=0 ;i<n ;i++ ){
        num = s[i] - '0' + 1;
        for(int j=1 ;j<=10 ;j++ ){
            for(int k=1 ;k<=10 ;k++ ){
                if(c[j][k][0]){
                    c[j][k][num] = true;
                }
            }
        }
        
        for(int j=1 ;j<=10 ;j++ ){
            if(c[j][0][0] == true){
                c[j][num][0] = true;
            }
        }
        
        c[num][0][0] = true;
        
    }
    
    for(int i=1 ;i<=10 ;i++ ){
        for(int j=1 ;j<=10 ;j++ ){
            for(int k=1 ;k<=10 ;k++ ){
                ans += c[i][j][k];
            }
        }
    }
    
    cout << ans << endl;
    return(0);
}

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

using namespace std;
const int MOD = 1000000007,MAX = 510000;
long int pow107 = (int)pow(10, 9) + 7,llimit = LONG_MAX,fac[MAX], finv[MAX], inv[MAX];
int ilimit = INT_MAX;

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long int COM(long int n,long int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

bool comp(pair<int, int> a, pair<int, int> b){
    if(a.first != b.first) return a.first > b.first;
    else return a.second < b.second;
}

long int jou(long int x, long int y){
    long int f = 1;
    for(int i = 0; i < y; ++i){
        f = f * x % pow107;
    }
    return f;
}

bool pn(long int x){
    if(x != 2 && x % 2 == 0)
        return false;
    for(int i = 3; i < x; ++i){
        if(x != i && x % i == 0)
            return false;
    }
    return true;
}

long int factorial(long int n){
    long int f = 1;
    for(long int i = 1; i <= n; ++i){
        f = f * i % pow107;
    }
    return f;
}

long int Func2(long int n,long int m){
    long int s2 = 1,
        r = 1;
    for(long int i = 1; i <= m; ++i){
        s2 = (s2*(n - (i - 1))/i) % (pow107);
    }
    return s2;
}

bool secsort(pair<int, int> a, pair<int, int> b){
    if(a.second == b.second)return a.first > b.first;
    else return a.second > b.second;
}

long int GCD(long int a,long int b){
    if(b == 0)return a;
    return GCD(b,a%b);
}

long int LCM(long int a,long int b){
    return a/GCD(a,b)*b;
}

//long intの最大llimit
//intの最大ilimit
//10^9+7    pow107
//素数pn
//n乗jou
//階乗factorial
//コンビネーションFunc2
//コンビネーションCOMinit(),COM(n,m)

int main(){
    int x,a,b;
    cin >> x >> a >> b;
    cout << (abs(x-a) < abs(x-b) ? "A" : "B") << endl;

}

Measured memory_bytes: 256
n = int(input())
s = list(input())
c = s[1:].count("E")
ans = c
for i in range(1, n):
    c -= (1 if s[i] == "E" else 0)
    c += (1 if s[i - 1] == "W" else 0)
    ans = min(c, ans)
print(ans)

Measured memory_bytes: 8056
#include <stdio.h>
int main(){
  int H,W,a,b,c,d,e;
  for(;;){ 
    scanf("%d%d",&H,&W);
      
    
    if(H==0&&W==0) break;
 
    for(a=0;W-1>=a;a++){
      printf("#");
     
    
      for(c=3;H>=c;c++){    
	if(a==W-1) printf("\n#");
	if(a==W-1) for(d=0;W-3>=d;d++){ printf(".");}
	if(a==W-1) printf("#");
      }

    }
  
      
    printf("\n");
    for(e=0;W-1>=e;e++){ printf("#");}
    printf("\n\n");
 
 }

  return 0;
}






  

 





Measured memory_bytes: 2040
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ld, ld> pdd;

void solve();

const int N = 2e5 + 10;

int main() {
    fast_cin();

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

void solve() {
    int n, k;
    cin >> n >> k;
    int a[N];
    for (int i=1; i <= n; i++) { 
        cin >> a[i];
    }

    vector<int> dp(N, 1e9 + 10);
    dp[1] = 0;
    for (int i=1; i <= n; i++) {
        for (int j=1; j <= k; j++) {
            if (i + j <= n) {
                dp[i+j] = min(dp[i+j], dp[i] + abs(a[i+j] - a[i]));
            }
        }
    }
    
    cout << dp[n] << '\n';
}


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

static const int MAX = 100000;
static const int INF = 1e9;

// 隣接リストを用いた幅優先探索 O(|V|+|E|)
int n;
vector<pair<int, int>> G[MAX]; // 頂点数がnのグラフを表す隣接リスト
vector<int> d(MAX, INF); // 始点sから頂点iまでの最短距離をd[i]に記録
// main関数からこれらを削除すること
 
bool bfs(int s) {
  queue<int> q;
  q.push(s);
  d[s] = 0;
  while(!q.empty()){
    int u = q.front();
    q.pop();
    for(int v = 0; v < G[u].size(); v++){
    if(d[G[u][v].first] == INF){
        d[G[u][v].first] = d[u] + G[u][v].second;
        q.push(G[u][v].first);
      }
    else if(d[G[u][v].first] != d[u] + G[u][v].second) return false;
    }
  }
  return true;
}

int main() {
// 重み付き無向(有向)グラフの隣接リスト
  int m, u, v, w;
  cin >> n >> m;
  
  for(int i = 0; i < m; i++){
    cin >> u >> v >> w;
    u--;
    v--;
    G[u].push_back(make_pair(v, w));
    G[v].push_back(make_pair(u, -w));
  }
  
  bool judge = true;
  for(int i = 0; i < n; i++){
    if(d[i] == INF) judge = bfs(i);
    if(judge == false){
      cout << "No" << endl;
      break;
    }
  }
  if(judge) cout << "Yes" << endl;
}

Measured memory_bytes: 9344
F=lambda x:x if P[x]<0else F(P[x]);N,M,*X=map(int,open(0).read().split());P=[-1]*-~N;S=N*~-N//2;r=[S]
while X:
 b,a=sorted(map(F,(X.pop(),X.pop())))
 if a!=b:S-=P[a]*P[b];P[a]+=P[b];P[b]=a
 r+=S,
print(*r[-2::-1],sep='\n')

Measured memory_bytes: 25076
N, M, C = map(int, input().split())
B = list(map(int,input().split()))
A = [[int(x) for x in input().split()] for i in range(N)]

cnt = 0

for i in range(N):
	sum = 0
	for j in range(M):
		sum += A[i][j] * B[j]
	if sum > -C:
		cnt += 1
print(cnt)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <iterator>
#include <math.h>
#include <cmath>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <regex>
#include <unordered_set>
#include <string>
#include <map>
#include <iomanip>
#include <sstream>
#include <cassert>
#include <time.h>
#include <numeric>
#include <complex>
  
using namespace std;
using ull = unsigned long long;
using ll = long long;
using ld = long double;
using D = double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
  
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define makeunique(x) sort(all(x)), (x).resize(unique(all(x)) - (x).begin())
#define rep(i, x)  for(int i = 0; i < (x); i++)
#define rrep(i, x) for(int i = (x - 1); i >= 0; i--)
#define sqrt(x) sqrt(abs(x))
#define y1 y1_1234413
#define j1 j1_235
#define y0 y0_235
#define j0 j0_256
#define fi first
#define se second
#define re return
#define prev PREV
#define next next
#define sz(x) ((int)x.size())
  
template<typename T> T sqr(T a) { re a * a; }
template<typename T> T gcd(T a, T b) { re b ? gcd(b, a % b) : a; }
template<typename T> T sgn(T a) { re a > 0 ? 1 : (a < 0 ? -1 : 0); }
template<typename T> T abs(T a) { re a > 0 ? a : -a; }
  
const ld st = 0.000001;
const ld pi = acos((ld)-1);
const int mod = 1e9 + 7;
  
#define FILENAME ""
  
const ll MAXN = 1000000 + 10;   

void add_self (int& a, int b) {
	a += b;
	if (a >= mod) {
		a -= mod;
	} 
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
//    freopen("symposium.in", "r", stdin);
//    freopen("symposium.out", "w", stdout);
    int n;
    cin >> n;
    vector <vector <int>> can(n, vector <int> (n));
    for (int i = 0; i < n; i++) {
    	for (int j = 0; j < n; j++) {
    		cin >> can[i][j];
    	}
    }
    vector <int> dp(1 << n);
    dp[0] = 1;
    for (int mask = 0; mask < (1 << n) - 1; ++mask) {
    	int a = __builtin_popcount(mask);
    	for (int b = 0; b < n; ++b) {
    		if (can[a][b] && !(mask & (1 << b))) {
    			int m2 = mask ^ (1 << b);
    			add_self(dp[m2], dp[mask]);
    		}
    	}
    }
    cout << dp[(1 << n) - 1];
    re 0;
}

Measured memory_bytes: 8448
#include <bits/stdc++.h>
using namespace std;
#define double long double
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define sp(p) cout<<setprecision(16)<<fixed<<p<<endl;
#define debug(x) cerr<<#x<<": "<<x<<endl;
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define rsort(a) sort(all(a),greater<>())
#define judge(f,y,n) cout<<(f?y:n)<<"\n";
#define debg(a) cout<<#a<<" "<<a<<endl;
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
template<class T>inline int out(const T &t){ print(t); putchar('\n'); return 0; }
template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> V;
const long long MOD=1000000007;
const long long INF = 1e18;
clock_t time_ini = clock();
double time_diff(){
  ll time_tmp = clock();
  const double time = static_cast<double>(time_tmp - time_ini) / CLOCKS_PER_SEC * 1000.0;
  return time;
}
#define saiaku if(time_diff() > 1990)
vector <ll> dp;

const string YES = "Yes";
const string NO = "No";

void solve_old(long long N, std::vector<long long> t, std::vector<long long> x, std::vector<long long> y){
    bool flg = false;
    for (ll i = 0; i < N; i++) {
        ll dt = (i ? t[i] - t[i-1] : t[i]);
        ll d = (i ? abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]) : abs(x[i]) + abs(y[i]));
        if (d <= dt && ((dt%2) == (d%2)) ) {
            flg = true;
        } else {
            flg = false;
            break;
        }
    }
    cout << (flg ? YES : NO) << "\n";
}

void solve(long long N, std::vector<long long> t, std::vector<long long> x, std::vector<long long> y){
    bool flg = true;
    for (ll i = 0; i < N; i++) {
        ll dt = (i ? t[i] - t[i-1] : t[i]);
        ll d = (i ? abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]) : abs(x[i]) + abs(y[i]));
        if (!(d <= dt && ((dt%2) == (d%2))) ) {
            flg = false;
            break;
        }
    }
    judge(flg, YES, NO);
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> t(N);
    std::vector<long long> x(N);
    std::vector<long long> y(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&t[i]);
        scanf("%lld",&x[i]);
        scanf("%lld",&y[i]);
    }
    solve(N, std::move(t), std::move(x), std::move(y));
    return 0;
}


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

#define uni(x)      (x).resize(unique(ALL(x)) - (x).begin())
#define fprint(v)   for(auto x : v) cout << x << ' '
#define ALL(x)      (x).begin(), (x).end()
#define MP(x, y)    make_pair(x, y)
#define SZ(x)       int((x).size())
#define PB(x)       push_back(x)
#define ll          long long
#define S           second 
#define F           first
#define nl          '\n'

using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
mt19937_64 rnd;

const int N = 2e5 + 5;

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1, 0);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    cout << (n - 1) / (k - 1) + ((n - 1) % (k - 1) != 0);
    return 0;
}
/*
    *** Most Impo.. -> check base case always
    1. Overflow Check (*, +)
    2. Index check (0 - based or 1 - based)
    3. Check for n = 1, 2, 3, 4....
    4. Corner Cases
*/

Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AOJ
{
	class Program
	{
		static void Main(string[] args)
		{
			var str = "";
			while ((str = Console.ReadLine()) != null)
			{
				var n = int.Parse(str);
				int count = 0;
				for (int a = 0; a <= 9; a++)
					for (int b = 0; b <= 9; b++)
						for (int c = 0; c <= 9; c++)
							for (int d = 0; d <= 9; d++)
								if ((a + b + c + d) == n)
									count++;
				Console.WriteLine(count);
			}
		}
	}
}

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

int main(){
  int n,m;
  cin >> n;
  int t[n+1]={};
  int sum = 0;

  for(int i=0;i<n;i++){
      cin >> t[i+1];
      sum += t[i+1]; //全ての問題を解くにあたってかかる時間の合計
  }

  cin >> m;
  for(int i=0;i<m;i++){
      int p,x;
      cin >> p >> x;
      cout << sum-t[p]+x << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(long long i=a; i<b; i+=1)
#define repr(i,a,b) for(long long i=a; i<=b; i+=1)
#define vec vector<ll>
#define map map<char,int>
#define repa(p,A) for(auto p:A)
#define pb push_back
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())
const double PI=acos(-1);
const ll INF=1000000;
using namespace std;

int main( ) {
    char A;
    cin>>A;
   if(A-'a'>=-32 && A-'a'<=-7) {
     cout<<'A'<<endl;
   }
   else cout<<'a'<<endl;
     
    }

Measured memory_bytes: 3632
#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;

vector<ll> A;

template<class T> void gc(T &x)
{
    char c;
    int s = 0;
    x = 0;

    c = getchar_unlocked();

    if (c == '-') s = 1;
    else if ('0' <= c && c <= '9')  x = c - '0';

    while (true)
    {
        c = getchar_unlocked();

        if (c < '0' || '9' < c) break;
        x = x * 10 + (c - '0');
    }

    if (s) x = -x;
}

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

    A.resize(K);

    REP(i, K) gc(A[i]);

    bool flg = true;
    ll maxa = 2;
    ll mina = 2;

    if (A[K - 1] == 2)
    {
        for (int i = K - 1; 0 <= i; i--)
        {
            if (maxa < A[i])
            {
                flg = false;
                break;
            }
            else
            {
                if (mina / A[i] == maxa / A[i]
                    && mina % A[i] != 0
                    && maxa % A[i] != 0)
                {
                    flg = false;
                    break;
                }
                else if (mina % A[i] == 0 && maxa % A[i] == 0)
                {
                    maxa = (maxa / A[i] + 1) * A[i] - 1;
                }
                else
                {
                    if (mina % A[i] != 0)
                    {
                        mina = (mina / A[i] + 1) * A[i];
                    }

                    maxa = (maxa / A[i] + 1) * A[i] - 1;
                }
            }
        }
    }
    else
    {
        flg = false;
    }

    if (flg) cout << mina << ' ' << maxa << endl;
    else cout << -1 << endl;

    return 0;
}


Measured memory_bytes: 1024
using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using System.Diagnostics;
using System.Numerics;
using Enu = System.Linq.Enumerable;

public class Program
{
    public void Solve()
    {
        int N = Reader.Int(), Avg = Reader.Int();
        var A = Reader.IntArray(N);
        var count = new long[N + 1, A.Sum() + 1];
        count[0, 0] = 1;
        long ans = 0;

        for (int i = 0, sum = 0; i < N; sum += A[i++])
            for (int used = i; used >= 0; used--)
                for (int s = 0; s <= sum; s++)
                {
                    count[used + 1, s + A[i]] += count[used, s];
                    if (Avg * (used + 1) == s + A[i]) ans += count[used, s];
                }

        Console.WriteLine(ans);
    }
}


class Entry { static void Main() { new Program().Solve(); } }
class Reader
{
    static TextReader reader = Console.In;
    static readonly char[] separator = { ' ' };
    static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;
    static string[] A = new string[0];
    static int i;
    static void Init() { A = new string[0]; }
    public static void Set(TextReader r) { reader = r; Init(); }
    public static void Set(string file) { reader = new StreamReader(file); Init(); }
    public static bool HasNext() { return CheckNext(); }
    public static string String() { return Next(); }
    public static int Int() { return int.Parse(Next()); }
    public static long Long() { return long.Parse(Next()); }
    public static double Double() { return double.Parse(Next()); }
    public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }
    public static int[] IntArray(int N) { return Range(N, Int); }
    public static int[][] IntTable(int H) { return Range(H, IntLine); }
    public static string[] StringArray(int N) { return Range(N, Next); }
    public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }
    public static string Line() { return reader.ReadLine().Trim(); }
    public static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; }
    static string[] Split(string s) { return s.Split(separator, op); }
    static string Next() { CheckNext(); return A[i++]; }
    static bool CheckNext()
    {
        if (i < A.Length) return true;
        string line = reader.ReadLine();
        if (line == null) return false;
        if (line == "") return CheckNext();
        A = Split(line);
        i = 0;
        return true;
    }
}

Measured memory_bytes: 3800
#include <bits/stdc++.h>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    int N;
    cin >> N;
    vector<int> P(N);
    for (int i = 0; i < N; i++) {
        cin >> P[i];
    }
    int ans = 0;
    int m = INF;
    REP(i, N){
        if(m > P[i]){
            ans++;
            m = P[i];
        }
    }
    pr(ans);
}

Measured memory_bytes: 1024
x = []
y = []
z = []
x = input().split()


y = input().split() 

z = input().split() 

waribiki = []
nest = []
for i in range(int(x[2])):
    waribiki = input().split()
    nest.append(waribiki)

inu = 0
neko = 0
nedan = []
for i in range(len(nest)):
    inu = int(nest[i][0])
    neko = int(nest[i][1])
    nedan.append(int(y[inu-1])+int(z[neko-1])-int(nest[i][2]))


may = int(min(y)) + int(min(z)) 

if len(nedan) > 1:
    print(min(nedan))
elif int(may) <= min(nedan):
    print(may)
else:
    print(nedan[0])

Measured memory_bytes: 54952
from heapq import heappop, heappush
X, Y, A, B, C = map(int, input().split())
h = []
for p in map(int, input().split()):
    heappush(h, (-p, 1))
for q in map(int, input().split()):
    heappush(h, (-q, 2))
for r in map(int, input().split()):
    heappush(h, (-r, 3))

ans = 0
cnt = 0
total = X + Y
while cnt < total:
    point, color = heappop(h)
    if color == 1:
        if X > 0:
            ans += -point
            X -= 1
            cnt += 1
    elif color == 2:
        if Y > 0:
            ans += -point
            Y -= 1
            cnt += 1
    elif color == 3:
        ans += -point
        cnt += 1
print(ans)


Measured memory_bytes: 49728
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
using ll=long long;
const ll MOD=100000007;
#define rep(i,a,b) for(ll i=a;i<b;i++)
inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline constexpr int intpow(ll a,ll b){
    if(b==0) return 1;
    ll ans=intpow(a,b/2);
    return ans*ans%MOD*(b&1?a:1)%MOD;
}
inline constexpr int modf(ll n){
    ll ans=1;
    rep(i,0,n) {ans=ans*(n-i)%MOD;}
    return ans;
}
int main(){
    vector<ll> h(5);
    ll ans=0;
    ll rem=10;
    rep(i,0,5) {
        cin>>h[i];
        ans+=h[i]/10*10;
        if(h[i]%10!=0) ans+=10;
        if(rem>h[i]%10&&h[i]%10!=0) rem=h[i]%10;
    }
    cout<<ans-10+rem;
}

Measured memory_bytes: 256
class UnionFind[T] {

  private[this] var map = Map.empty[T, T];

  def addEdge(parent: T, child: T): Unit = {
    map = map + (child -> parent);
  }

  def fetchRoot(elem: T): T = {
    @scala.annotation.tailrec
    def sub(elem: T, pendings: List[(T, T)]): T = {
      map.get(elem) match {
        case None =>
          pendings.foreach { case (c, p) =>
            map = map + (c -> elem);
          }
          elem;
        case Some(p) =>
          sub(p, (elem, p) :: pendings);
      }
    }
    sub(elem, Nil);
  }

}

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n, m = sc.nextInt();
  val ps = Array.fill(n)(sc.nextInt());
  val xys = Array.fill(m)((sc.nextInt(), sc.nextInt()));

  val unionFind = new UnionFind[Int];
  xys.foreach { case (x, y) =>
    val xr = unionFind.fetchRoot(x);
    val yr = unionFind.fetchRoot(y);
    if (xr != yr) {
      unionFind.addEdge(yr, xr);
    }
  }

  val answer = ps.zipWithIndex.count { case (p, i) =>
    unionFind.fetchRoot(p) == unionFind.fetchRoot(i + 1);
  }
  println(answer);
}

Measured memory_bytes: 91800
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

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

using namespace std;


int dx[256];
int dir[100];
int pos[100];
int main(){
	dx['L'] = -1;
	dx['R'] = 1;

	int n, l;
	while(cin >> n >> l, n|l){
		rep(i, n){
			char c;
			cin >> c >> pos[i];
			dir[i] = dx[c];
		}

		int cnt = n;
		int time = 0;
		int last = -1;
		while(1){
			rep(i, n){
				if(pos[i] == l){
					pos[i] = 1<<29;
					last = i;
					cnt--;
				}
			}
			rep(i, n){
				if(pos[i] == 0){
					pos[i] = 1<<29;
					last = i;
					cnt--;
				}
			}
			if(!cnt) break;

			rep(i, n){
				pos[i] += dir[i];
			}
			time++;

			rep(i, n){	// meets
				rep(j, i){
					if(pos[i] == pos[j]){
						dir[i] *= -1;
						dir[j] *= -1;
					}
				}
			}
		} // end while

		cout << time << ' ' << last+1 << endl;
	}


	return 0;
}

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



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.flush();
	ll t=1;
	//cin>>t;
	while(t--)
	{
		ld a,b;
		cin>>a>>b;
		
		ll a1=round(100*a/8.0);
		
		ll a2=(ll)(10*b); // 10
		//cout<<a1<<" "<<a2<<endl;
		ll z1=round(a1*8/100);
		ll z2=round(a1/10);
		ll p1=0;
		ll y1=round(a2*8/100);
		ll y2=round(a2/10);
		ll p2=0;
		if(z1==a && z2==b)
		{
			p1=1;
			}
		if(y1==a && y2==b)
		{
			p2=1;
			}
		
		if(p1==0 && p2==0)
		{
			//cout<<a2;
			cout<<"-1"<<endl;
			}
		else
		{
			//cout<<"-1";
			ll ans;
			if(p1==1 && p2==0)
			{
				ans=a1;
				}
			else if(p1==0 && p2==1)
			{
				ans=a2;
				}
			else 
			{
				ans=min(a1,a2);
				}
			
			cout<<ans<<endl;
			}
		
		//cout<<ans<<endl;
	}
	
	
return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
using namespace std;
using lli = long long int;

lli pow(lli x, lli y, lli m) {
  x %= m;
  lli res = 1;
  while (y > 0) {
    if ((y & 1) == 1) {
      res = res * x % m;
    }
    x = x * x % m;
    y >>= 1;
  }
  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  lli m = 1000000007;
  lli n;
  string s;
  cin >> n >> s;
  lli ls = s.size();
  vector<vector<lli>> dp(n+1, vector<lli>(n+1, 0));
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
      if (j == 0) {
        dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % m;
      } else if (j < n) {
        dp[i][j] = (dp[i-1][j+1] + dp[i-1][j-1] * 2) % m;
      } else {
        dp[i][j] = dp[i-1][j-1] * 2 % m;
      }
    }
  }
  lli res = dp[n][ls] * pow(2, (m-2)*ls, m) % m;
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 195840
#include <bits/stdc++.h>
using namespace std;
int main(){
  long N;cin>>N;
  vector<long>A(N);
  bool jud = false;
  for (int i=0; i<N; i++) cin >> A[i];
  sort(A.begin(), A.end());
  for (int i=0; i<N-1; i++){
    if (A[i+1]-A[i] == 0){
      jud = true;
      cout << "NO" << endl;
      break;
    }
  }
  if (jud == false) cout << "YES" << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Graph= vector<vector<int>>; 
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
#define fi first
#define se second 
#define set20 cout<<fixed<<setprecision(20) ;
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
double pi=acos(-1) ;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}


int main(){
 ll d ; cin>> d ;
 ll c[26] ; rep(i,26) cin>>c[i] ;
 ll s[d][26] ;
 rep(i,d){
     rep(j,26){
        cin>> s[i][j] ;
     }
 }

ll ans=0 ;
 rep(i,d){
     cout<< (i%26)+1 <<endl ;
 }
 return 0 ; 
}



Measured memory_bytes: 3708
#include<bits/stdc++.h>
using namespace std;
int main(){
  int A,B,C,D,E;
  cin>>A>>B>>C>>D>>E;
  
vector<int>vec={A,B,C,D,E};
  int min=10;
  for(int i=0;i<vec.size();i++){
    if(vec.at(i)%10!=0&&min>=vec.at(i)%10){
      min=vec.at(i)%10;
    }
  }
  
    int sum1=0;
    int sum2=0;
    int sum3=0;
    int sum4=0;
    for(int j=0;j<vec.size();j++){
      if((vec.at(j)%10!=0&&vec.at(j)%10!=min)||(vec.at(j)%10==min&&sum4>0)){
        sum1+=vec.at(j);
        
        sum2+=vec.at(j)%10;
        
        sum3++;
      }
      else if(vec.at(j)%10==min&&sum4==0){
        sum1+=vec.at(j);
        sum4++;
      }
      else if(vec.at(j)%10==0){
        sum1+=vec.at(j);
    
    }
    }
  
    cout<<sum1+10*sum3-sum2<<endl;
  }

    
          


Measured memory_bytes: 256
fun main(args: Array<String>) {
  val (n, aRaw, bRaw, cRaw, dRaw) = readLine()!!.split(" ").map { it.toInt() }
  val a = aRaw - 1
  val b = bRaw - 1
  val c = cRaw - 1
  val d = dRaw - 1
  val s = readLine()!!

  fun isGoodRange(from: Int, inclusiveTo: Int): Boolean {
    for (i in (from + 1)..(inclusiveTo - 2)) {
      if (s[i] == '#' && s[i + 1] == '#') {
        return false
      }
    }
    return true
  }

  fun solve(): Boolean {
    if (c < d) {
      return isGoodRange(a, c) && isGoodRange(b, d)
    } else {
      if (!isGoodRange(a, c) || !isGoodRange(b, d)) {
        return false
      }
      var ok = false
      for (i in b..d) {
        if (s[i - 1] == '.' && s[i] == '.' && s[i + 1] == '.') {
          ok = true
        }
      }
      return ok
    }
  }

  println(if (solve()) "Yes" else "No")
}

Measured memory_bytes: 41660
# AOJ ITP1_9_A

# ※大文字と小文字を区別しないので注意！！！！
# 全部大文字にしちゃえ。
def main():
    W = input().upper()  # 大文字にする
    line = ""
    count = 0
    while True:
        line = input().split(" ")
        if line[0] == "END_OF_TEXT": break
        for i in range(len(line)):
            word = line[i].upper()
            if W == word: count += 1
    print(count)

if __name__ == "__main__":
    main()

# Accepted.


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

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

#define pb push_back
#define in ,
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}


int main() {
  int n;
  while(cin >> n) {
    if(n == 0) return 0;
    int s[1000], p[1000], q[1000], r[1000];
    rep(i, 0, n) cin >> s[i] >> p[i] >> q[i] >> r[i];
    int C, P, Q, R;
    cin >> P >> Q >> R >> C;
    int f = 0;
    rep(i, 0, n) {
      if(p[i] > P || q[i] > Q || r[i] > R) continue;
      int sum = p[i] * 4 + q[i] * 9 + r[i] * 4;
      if(sum > C) continue;
      f = true;
      cout << s[i] << endl;
    }
    if(!f) cout << "NA" << endl;
  }
}

Measured memory_bytes: 3192
//Har Har Mahadev
using namespace std;
#include <bits/stdc++.h>
#define booga cout << "booga" << endl
#define ll long long int
#define pb push_back
#define mp make_pair
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " -> " << a << endl;
	err(++it, args...);
}

void testcase(){
	string s;
	cin >> s;
	int ans = 0,cnt = 0;
	for(int i{0};i < 3;i++){
		if(s[i] == 'R'){
			cnt++;
		}
		else{
			cnt = 0;
		}
		ans = max(ans,cnt);
	}
	cout << ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	while(t--){
		testcase();
	}
	return 0;
}


Measured memory_bytes: 3648
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
  long long int n;
  cin >> n;
  long long int count = 0;
  if(n < 10){
    count = n;
  }
  else if(n >= 10 && n < 100){
    count = 9;
  }
  else if(n >= 100 && n < 1000){
    count = 9;
    long long int a = n-99;
    count += a;
  }
  else if(n >= 1000 && n < 10000){
    count = 909;
  }
  else if(n >= 10000 && n < 100000){
    count = 909;
    long long int a = n-9999;
    count += a;
  }
  else if(n == 100000){
    count = 90909;
  }
  cout << count << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <tuple>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <climits>
#include <numeric>
#include <queue>
#include <cmath>
#include <iomanip>
#include <array>
#include <string>
#include <stack>
#include <cassert>
#include <memory>
#include <random>
#include <fstream>
#include <cfloat>

struct Camel {
	int k, l, r;
};
int main() {
	int test_case; std::cin >> test_case;
	const auto comparator = [](const Camel& a, const Camel& b) { return a.l - a.r < b.l - b.r; };
	for (auto _t = 0; _t < test_case; ++_t) {
		int n; std::cin >> n;
		std::vector<Camel> camels(n);
		for (auto& c : camels) std::cin >> c.k >> c.l >> c.r;
		std::vector<Camel> normal, reverse;
		for (const auto& c : camels) {
			if (c.l >= c.r) {
				normal.push_back(c);
			}
			else {
				reverse.push_back(c);
			}
		}
		std::sort(normal.rbegin(), normal.rend(), comparator);
		std::sort(reverse.begin(), reverse.end(), comparator);
		std::set<int, std::greater<int>> backward;
		std::set<int> forward;
		for (auto i = 1; i <= normal.size(); ++i) {
			backward.insert(i);
		}
		for (auto i = normal.size() + 1; i <= n; ++i) {
			forward.insert(i);
		}
		long long int sum{ 0 };
		for (const auto& c : normal) {
			const auto pos = backward.lower_bound(c.k);
			if (pos == backward.end()) {
				backward.erase(backward.begin());
				sum += c.r;
			}
			else {
				backward.erase(pos);
				sum += c.l;
			}
		}
		for (const auto& c : reverse) {
			const auto pos = forward.upper_bound(c.k);
			if (pos == forward.end()) {
				forward.erase(forward.begin());
				sum += c.l;
			}
			else {
				forward.erase(pos);
				sum += c.r;
			}
		}
		std::cout << sum << '\n';
	}
}


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

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

Measured memory_bytes: 3612
#include <cstdio>
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>

#define MAX_N 200000
typedef long long int ll;
using namespace std;
int main(){
    ll n;
    cin >> n;
    ll a[MAX_N];
    ll a_max=0;
    ll arg_max;
    ll a_second_max=0;
    for(ll i=0;i<n;i++){
        cin >> a[i];
    }
    for(ll i=0;i<n;i++){
        if(a[i]>a_max){
            arg_max=i;
            a_max=a[i];
        }
    }
    for(ll i=0;i<n;i++){
        if(i!=arg_max){
            a_second_max = max(a[i],a_second_max);
        }
    }

    for(ll i=0;i<n;i++){
        if(i==arg_max){
            cout<<a_second_max<<endl;
        }else{
            cout<<a_max<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3200
def dfs(v):
    global adjacency_mat, visited
    st = [] # stack
    st.append(v)
    while st:
        # stackから取り出す
        h = st.pop()
        visited[h] = True
        for i in range(N):
            # 辺がないなら何もしない
            if adjacency_mat[h][i] == None:
                continue
            # すでに到達したことがあるなら何もしない
            if visited[i] == True:
                continue
            # stackに加える
            st.append(i)

if __name__ == "__main__":
    N, M = map(int, input().split())
    list_ab = [[] for _ in range(M)]
    adjacency_mat = [[None]* N for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        list_ab[i].append(a-1)
        list_ab[i].append(b-1)
        adjacency_mat[a-1][b-1] = 1
        adjacency_mat[b-1][a-1] = 1
        
    ans = 0
    for a, b in list_ab:
        visited = [False] * N
        # ある辺をなくす
        adjacency_mat[a][b] = None
        adjacency_mat[b][a] = None
        # 全ての辺を訪れることができるかどうか探索
        dfs(0)
        # 全ての辺を訪れることができるかどうか
        if sum(visited) < N:
            ans += 1
        # 元に戻す
        adjacency_mat[a][b] = 1
        adjacency_mat[b][a] = 1
    print(ans)

Measured memory_bytes: 3064
T1,T2=map(int,input().split())
A1,A2=map(int,input().split())
B1,B2=map(int,input().split())
a1=A1*T1
a2=A2*T2
b1=B1*T1
b2=B2*T2
if a1+a2==b1+b2:
    print("infinity")
else:
    if a1>b1 and a2<b2:
        if a1+a2<b1+b2:
            if (a1-b1)%(-a1-a2+b1+b2)==0:
                print((a1-b1)//(-a1-a2+b1+b2)*2)
            else:
                print((a1-b1)//(-a1-a2+b1+b2)*2+1)
        else:
            print(0)
    elif a1<b1 and a2>b2:
        if a1+a2>b1+b2:
            if (b1-a1)%(a1+a2-b1-b2)==0:
                print((b1-a1)//(a1+a2-b1-b2)*2)
            else:
                print((b1-a1)//(a1+a2-b1-b2)*2+1)
        else:
            print(0)
    else:
        print(0)

Measured memory_bytes: 3192
#include <iostream>

using namespace std;
using ll = long long;


const int n = 100001;
bool sieve[n];
int cnt[n];

int main(){
    for (int i = 0; i < n; ++i) sieve[i] = true;
    sieve[0] = false;
    sieve[1] = false;
    for (int i = 2; i < n; ++i) 
        if(sieve[i]) for(int k = i + i; k < n; k += i) sieve[k] = false;

    cnt[0] = 0;
    for (int i = 1; i < n; ++i) {
        if (i % 2 == 0) cnt[i] = cnt[i - 1];
        else if (sieve[i] && sieve[(i + 1) / 2]) cnt[i] = cnt[i - 1] + 1;
        else cnt[i] = cnt[i - 1];
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        cout << cnt[r] - cnt[l - 1] << endl;
    }
}

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

int main(){
    string s,t;
    int a,b,c,d;
    cin >> s >>t;
    a = s.length();
    b = t.length();
    d = 0;
    for(int i=0;i<a-b+1;i++){
        c = 0;
        for(int ii=0;ii<b;ii++){
            int iii = ii+i;
            if(s.at(iii)!=t.at(ii)){
                c++;
            }
        }
        if(i == 0){
            d = c;
        }
        if(d >= c){
            d = c;
        }
    }
    cout << d;
}

Measured memory_bytes: 3636
N = int(input())
S = input()
ss = [0]*N

if S.count(S[0]) == N:
  print(1)

else:
  for i in range(1, N):
    X = "".join(set(S[:i]))
    Y = "".join(set(S[i:]))
    for j in range(len(X)):
      if X[j] in Y:
        ss[i] += 1
  
  print(max(ss))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
 
int main()
{
  int N;
  cin >> N;
  vector<string> A(N);
  REP(i, N) cin >> A[i];
  
  sort(ALL(A));
  int cnt = 1;
  int MAX = 0;

  REP(i,N-1){
    if(A.at(i) == A.at(i+1)){
      cnt++;
    }else{
      MAX = max(MAX,cnt);
      cnt = 1;
    }
  }
  MAX = max(MAX,cnt);
  cnt = 1;
  REP(i,N-1){
    if(A.at(i) == A.at(i+1)){
      cnt++;
    }else{
      if(cnt == MAX){
        cout << A.at(i) << endl;
      }
      cnt = 1;
    }
  }
  if(cnt == MAX){
    cout << A.at(N-1) << endl;
  }
}

Measured memory_bytes: 14208
import std.stdio;
import std.algorithm;
import std.array;
import std.conv;
import std.datetime;
import std.numeric;
import std.math;
import std.string;

string my_readln() { return chomp(readln()); }

void main()
{
	auto tokens = my_readln().split();
	auto N = tokens[0].to!ulong;
	uint[4] a;
	foreach (token; my_readln.split)
	{
		++a[token.to!uint];
	}

	double[uint[4]] memo;
	auto dp = new double[][][](305, 305, 305);
	foreach (i; 0..N+1)
	{
		foreach (j; 0..N+1)
		{
			foreach (k; 0..N+1)
			{
				if (i == 0 && j == 0 && k == 0)
				{
					dp[i][j][k] = 0.0;
					continue;
				}

				auto p3 = i / cast(double)N;
				auto p2 = j / cast(double)N;
				auto p1 = k / cast(double)N;
				auto p123 = p1 + p2 + p3;
				auto p = 1.0 / p123;
				if (i != 0)
					p += dp[i-1][j+1][k] * p3 / p123;
				if (j != 0)
					p += dp[i][j-1][k+1] * p2 / p123;
				if (k != 0)
					p += dp[i][j][k-1] * p1 / p123;
				dp[i][j][k] = p;
			}
		}
	}

	writefln("%.10f", dp[a[3]][a[2]][a[1]]);
	stdout.flush();
}

Measured memory_bytes: 377340
N = int(input())
A = [[0, 0, 0]] + [[int(i) for i in input().split()] for _ in range(N)]

for (t, x, y), (nt, nx, ny) in zip(A[:N], A[1:]):
    d = abs(x - nx) + abs(y - ny)
    r = nt - t
    if d > r or d % 2 != r % 2:
        print("No")
        quit()
print("Yes")

Measured memory_bytes: 22628