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

using i64 = long long;
using P = pair<i64, i64>;

#define overload3(_1, _2, _3, name, ...) name
#define rep1(i, n) for(i64 i = 0LL; i < (n); ++i)
#define rep2(i, a, b) for(i64 i = (a); i < (b); ++i)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define all(v) v.begin(), v.end()

const string YES = "YES";
const string NO = "NO";

void solve(long long A, long long V, long long B, long long W, long long T){
    if(abs(A - B) <= (V - W) * T) cout << YES << endl;
    else cout << NO << endl;
}

struct IoSetup {
    IoSetup() {
        // cin.tie(nullptr);
        // ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

int main(){
    long long A;
    scanf("%lld",&A);
    long long V;
    scanf("%lld",&V);
    long long B;
    scanf("%lld",&B);
    long long W;
    scanf("%lld",&W);
    long long T;
    scanf("%lld",&T);
    solve(A, V, B, W, T);
    return 0;
}


Measured memory_bytes: 3684
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int hx, mx, hy, my, k;
    cin >> hx >> mx >> hy >> my >> k;
    mx += hx * 60; my += hy * 60;
    cout << my - mx  - k << endl;
    return 0; 
}

Measured memory_bytes: 3600
import fractions

N, X = [int(elem) for elem in input().split()]
xs = [int(elem) for elem in input().split()]

xs.append(X)
xs = sorted(xs)

diff = []
for x1, x2 in zip(xs[:-1], xs[1:]):
  diff.append(x2 - x1)

if len(diff) > 1:
  res = fractions.gcd(diff[0], diff[1])
  for elem in diff[2:]:
    res = fractions.gcd(res, elem)
  print(res)
else:
  print(diff[0])

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

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n;
    vector<ld> a(n);
    for (int i = 0; i < n; i++) {
        int ai; cin >> ai;
        a[i] = (ld)ai;
    }
    sort(a.begin(),a.end());
    for (int i = 1; i < n; i++) {
        a[i] = (a[i]+a[i-1])/2;
    }
    cout << fixed << setprecision(10) << (a[n-1]) << '\n';

}



Measured memory_bytes: 256
using System;

namespace Volume0_0022
{
    class Program
    {
        static void Main(string[] args)
        {
            int count;
            while( (count = Convert.ToInt32(Console.ReadLine())) != 0 )
            {
                int max = -100001, sum = 0;
                for (var i = 0; i < count; i++)
                {
                    int num = Convert.ToInt32(Console.ReadLine());
                    sum += num;
                    max = Math.Max(sum, max);
                    sum = sum < 0 ? 0 : sum;
                }
                Console.WriteLine(max);
            }
        }
    }
}

Measured memory_bytes: 9256
using System;
					
public class Program
{
	public static void Main()
	{
		int[] ar = Array.ConvertAll(Console.ReadLine().Split(' '), arTemp => Convert.ToInt32(arTemp));
      	
      	double totalApplePieceAmount = (double)(ar[0] * 3 + ar[1]);
		
      
      	Console.WriteLine(Math.Floor(totalApplePieceAmount / 2.0));
	}
}

Measured memory_bytes: 11220
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
long double pi = 3.14159265358979;
int main() {
	double a, b, x;
	cin >> a >> b >> x;
	x = x / a * 2;
	if (a * b >= x) {
		a = x / b;
		cout << fixed << setprecision(16) << atan(b / a) * 180 / pi << endl;
		return 0;
	}
	else {
		x = a * b * 2 - x;
		b = x / a;
		cout << fixed << setprecision(16) << atan(b / a) * 180 / pi << endl;
	}
}

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

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

    int a=L[0],b,sum=L[0];
    for(int i=1;i<N;i++){
        if(a<L[i]){
            a=L[i];
        }
        sum+=L[i];
    }
    if(2*a<sum) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

using namespace std;

#define int long long
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(i, a) for (auto &i: (a))
#define sz(x) (int)(x).size()
#define all(v) (v).begin(), (v).end()
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)

void solve();

signed main () {
    clock_t beg = clock();
    cout << fixed << setprecision(15);
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif 
    int t = 1; 
    // cin >> t;    
    int tt = t;
    while (t--) {
        // cout << "Case #" << tt - t << ": "; 
        solve();
    }
    cerr << "\nExecution time: " << (clock() - beg) / 1000 << '\n';
    return 0;
}
const int N = 3005;
pair<int, int> dp[N][N];
string a, b;
int lcs (int i, int j) {
    if (i < 0 or j < 0)
        return 0;
    if (dp[i][j] != make_pair(-1ll, -1ll))
        return dp[i][j].first;
    array<int, 3> arr({lcs(i - 1, j), lcs(i, j - 1), (a[i] == b[j]) + lcs(i - 1, j - 1)});
    int mx = -1;
    int val;
    for (int k = 0; k < 3; ++k) if (arr[k] > mx) mx = arr[k], val = k;
    dp[i][j] = make_pair(mx, val);
    return dp[i][j].first;
}
string reconstruct (int i, int j) {
    if (i < 0 or j < 0) {
        return "";
    }
    string ans;
    int which = dp[i][j].second;
    if (which == 0) {
        ans = reconstruct(i - 1, j);
    } else if (which == 1) {
        ans = reconstruct(i, j - 1);
    } else {
        ans = reconstruct(i - 1, j - 1);
        if (a[i] == b[j])
            ans += a[i];
    }
    return ans;
}
void solve() {
    cin >> a >> b;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            dp[i][j] = {-1, -1};
    auto lol = lcs((int) a.size() - 1, (int) b.size() - 1);
    cout << reconstruct((int) a.size() - 1, (int) b.size() - 1);
}                   

Measured memory_bytes: 145584
L =[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 = int(input())
print (L[K-1])

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main(){
	long long int dp[31];
	dp[0]=1;
	dp[1]=1;
	dp[2]=2;
	for(int i=3;i<=30;i++)dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
	int n;
	while(cin>>n,n){
		long long int ans=dp[n];
		ans=(ans-1)/10+1;
		ans=(ans-1)/365+1;
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#define ll long long
#define INF (ll)(1e18 + 2)
using namespace std;

int main() {
  ll n, k, ne = 0, po = 0, nu = 0;
  scanf("%lld %lld", &n, &k);
  vector<ll> a(n);
  for(int i = 0; i < n; i++) {
    scanf("%lld", &a[i]);
    if(a[i] < 0)
      ne++;
    else if(a[i] > 0)
      po++;
    else
      nu++;
  }
  sort(a.begin(), a.end());
  if(k <= ne * po) {
    ll ok = -INF, ng = 0;
    while(ok + 1 != ng) {
      ll t = (ok + ng) / 2, num = 0;
      for(int i = 0; i < ne; i++) {
        auto it = upper_bound(a.begin(), a.end(), t / a[i]);
        num += n - distance(a.begin(), it);
      }
      if(num < k)
        ok = t;
      else
        ng = t;
    }
    printf("%lld\n", ok);
  } else if(k <= ne * po + nu * (ne + po) + nu * (nu - 1) / 2)
    printf("0\n");
  else {
    k -= ne * po + nu * (ne + po) + nu * (nu - 1) / 2;
    ll ok = 0, ng = INF;
    while(ok + 1 != ng) {
      ll t = (ok + ng) / 2, num = 0;
      for(int i = 0; i < n; i++) {
        if(!a[i]) continue;
        if(a[i] < 0) {
          auto it = upper_bound(a.begin(), a.end(), (-t + a[i] + 1) / (-a[i]));
          num += ne - distance(a.begin(), it);
          if(*it <= a[i]) num--;
        } else {
          auto it = lower_bound(a.begin(), a.end(), (t + a[i] - 1) / a[i]);
          num += distance(a.begin(), it) - ne - nu;
          if(*it > a[i] || it == a.end()) num--;
        }
      }
      num /= 2;
      if(num < k)
        ok = t;
      else
        ng = t;
    }
    printf("%lld\n", ok);
  }
}

Measured memory_bytes: 1792
var
  s,t:ansistring;
 function sum(x:ansistring):longint;
  var
    i,j,ans,max:longint;
    y:ansistring;
  begin
    max:=0;
    for i:=1 to length(s)-length(x)+1 do
      begin
        y:=copy(s,i,length(x));ans:=0;
        for j:=1 to length(x) do if x[j]=y[j] then inc(ans);
        if ans>max then max:=ans;
      end;
    exit(max);
  end;
begin
  readln(s);
  readln(t);
  writeln(length(t)-sum(t));
end.

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

int main()
{
  while(true)
  {
    int n;
    cin >> n;
    if ( n == 0 ) break;

    int i;
    for (i=0; n!=1; i++)
    {
      if ( n%2 == 0 )
      {
        n /= 2;
      }
      else
      {
        n = n * 3 + 1;
      }
    }
    cout << i << endl;
  }
}

Measured memory_bytes: 1160
#include <iostream>
#include <string>
#include <array>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <cctype>
#include <map>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <ctype.h>


#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define FOR(i,l,r) for(size_t i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)



using namespace std;

bool is_integer( float x ){
    return floor(x)==x;
}


int main() {
    string s; cin >> s;
    int n = s.length();
    map<char,bool>mp;
    mp['N'] = false;
    mp['W'] = false;
    mp['S'] = false;
    mp['E'] = false;
    int ans = false;


    for(int i = 0; i < n; i ++){
        mp[s[i]] = true;
    }

    if(mp['N'] && mp['W'] && mp['S'] && mp['E']) ans = true;
    if(mp['N'] && !mp['W'] && mp['S'] && !mp['E']) ans = true;
    if(!mp['N'] && mp['W'] && !mp['S'] && mp['E']) ans = true;

    cout << ((ans)?"Yes":"No");

    return 0;
}











Measured memory_bytes: 3588
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <fstream>
#include <chrono>
#include <random>
#include <bitset>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)(x).size())
#define pb push_back
using ll = long long;
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}

int D=365;
vector<int> c(26);
vector<vector<int>> s(365, vector<int>(26));

ll calc(const vector<int>& t, int d, int q){
  ll res = 0;
  vector<int> lst(26,-1);
  rep(i,D){
    if(i!=d){
      res += s[i][t[i]];
      lst[t[i]] = i;
    }
    else{
      res += s[i][q];
      lst[q]=i;
    }
    rep(j,26){
      res -= c[j]*(i-lst[j]);
    }
  }
  return res;
}



int main(){

  /*
  ifstream in("input.in");
  cin.rdbuf(in.rdbuf());
  ofstream ofs("output.txt");
  cout.rdbuf(ofs.rdbuf());
  //*/
  chrono::system_clock::time_point start, end;
  start = chrono::system_clock::now();
  mt19937 mt(14);
  cin >> D;
  rep(i,26) cin >> c[i];
  rep(y,D) rep(x,26) cin >> s[y][x];
  vector<int> t(D,0);
  vector<int> ids;
  rep(i,26) if(c[i]>20) ids.pb(i);
  rep(d,D){
    t[d] = ids[d%sz(ids)];
  }
  ll now = calc(t, -1, -1);
  while(1){
    int d=mt()%365, q=mt()%26;
    if(now<calc(t,d,q)){
      t[d]=q;
    }
    // timer
    end = chrono::system_clock::now();
    double ela = chrono::duration_cast<chrono::milliseconds> (end-start).count();
    if(ela>1800) break;
  }
  rep(i,D) cout << t[i]+1 << '\n';
  return 0;
}


Measured memory_bytes: 3648
def c_Candies(N, A):
    dp = [[0] * N for _ in range(2)]
    dp[0][:] = A[0][:]
    dp[1][0] = A[0][0] + A[1][0]
    for i in range(2):
        for j in range(1, N):
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + A[i][j]
    return dp[1][-1]

N = int(input())
A = [[int(i) for i in input().split()] for j in range(2)]
print(c_Candies(N, A))

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

int main() {
  int n; cin>>n;
  vector<ll> a(n),b(n),c(n);
  rep(i, n) scanf("%lld", &a[i]);
  rep(i, n) scanf("%lld", &b[i]);
  rep(i, n) scanf("%lld", &c[i]);
  
  sort(a.begin(), a.end());
  sort(c.begin(), c.end());

  ll res=0;
  rep(i, n) {
    ll top=lower_bound(a.begin(), a.end(), b[i])-a.begin();
    ll down=upper_bound(c.begin(), c.end(), b[i])-c.begin();
    down=(ll)(n)-down;
    res+=top*down;
  }
  printf("%lld\n", res);
}


Measured memory_bytes: 2560
package main

import (
	"fmt"
)

func main() {
	var n, a, b int
	var ans int
	fmt.Scan(&n, &a, &b)

	switch {
	case n < a+b:
		if n > a {
			ans = a
		} else {
			ans = n
		}
	case n%(a+b) == 0:
		ans = a * (n / (a + b))
	case n%(a+b) != 0:
		if remainder := n % (a + b); remainder < a {
			ans = a*(n/(a+b)) + remainder
		} else if remainder > a {
			ans = a * (n/(a+b) + 1)
		}
	}
	fmt.Println(ans)
}

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

n, c = map(int, input().split())
sushi = [tuple(map(int, input().split())) for _ in range(n)]

ans = 0

cand1 = [0] * n
v_sum = 0
for i in range(n):
    v_sum += sushi[i][1]
    cand1[i] = v_sum - sushi[i][0]
    if i > 0:
        cand1[i] = max(cand1[i], cand1[i-1])

cand2 = [0] * n
v_sum = 0
for i in reversed(range(n)):
    v_sum += sushi[i][1]
    cand2[i] = v_sum - (c - sushi[i][0])
    if i != n - 1:
        cand2[i] = max(cand2[i], cand2[i+1])

ans = max(ans, max(cand1), max(cand2))

v_sum = 0
for i in reversed(range(1, n)):
    v_sum += sushi[i][1]
    ans = max(ans, v_sum - (c - sushi[i][0]) * 2 + cand1[i-1])

v_sum = 0
for i in range(n-1):
    v_sum += sushi[i][1]
    ans = max(ans, v_sum - sushi[i][0] * 2 + cand2[i+1])

print(ans)


Measured memory_bytes: 24540
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        int X = sc.nextInt();

        int ans = 0;
        for (int i = 0; i <= A; i++) {
            for (int j = 0; j <= B; j++) {
                for (int k = 0; k <= C; k++) {
                    int sum = 500*i + 100*j + 50*k;
                    if (sum == X) {
                        ans++;
                        break;
                    }
                    if (sum > X) break;
                }
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;

void main() {
    string s;
    scan(s);

    int n = s.length.to!int;

    auto tp = new int[](n + 1);
    tp[0] = 1;
    foreach (i; 1 .. n + 1) {
        tp[i] = tp[i-1] * 10 % 2019;
    }

    long ans;
    int t;
    auto cnt = new int[](2020);
    cnt[0] = 1;

    foreach (i; 0 .. n) {
        (t += (s[n - 1 - i] - '0') * tp[i]) %= 2019;
        ans += cnt[t];
        cnt[t]++;
    }

    writeln(ans);
}

void scan(T...)(ref T args) {
    auto line = readln.split; // @suppress(dscanner.suspicious.unmodified)
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront;
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args)
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args)
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    return isChanged;
}

void yes(bool ok, string y = "Yes", string n = "No") {
    return writeln(ok ? y : n);
}


Measured memory_bytes: 3704
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int,int>P;


int A,B,C,X,Y;

int c1()
{
	return A*X+B*Y;
}

int c2()
{
	return min(X,Y)*2*C+(max(X-X,X-Y)*A)+(max(Y-X,Y-Y)*B);
}

int c3()
{
	return max(X,Y)*2*C;
}

int main()
{
	cin>>A>>B>>C>>X>>Y;
	vector<int>t={c1(),c2(),c3()};
	cout<<min(t[0],min(t[1],t[2]))<<endl;

}

Measured memory_bytes: 256
namespace ABC123
{
    using System;
    using static System.Console;
    using System.Collections.Generic;
    class Program
    {
        static void Main(string[] args)
        {
            var anntenas = new List<int>();
            for (int i = 0; i < 5; i++)
            {
                anntenas.Add(ReadInput());
            }
            var k = ReadInput();

            for (int i = 0; i < 5; i++)
            {
                for (int j = 0; j < 5; j++)
                {
                    if (Math.Abs(anntenas[i] - anntenas[j]) > k)
                    {
                        WriteLine(":(");
                        return;
                    }
                }
            }

            WriteLine("Yay!");
        }

        static int ReadInput()
        {
            return int.Parse(ReadLine());
        }
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <vector>
using namespace std;
int main() {
    
    vector<char> ret;

    ret.resize(210000);
    int start = ret.size()-1;
    string str;
    cin>>str;
    for(int i=0;i<str.length();i++){
        ret.push_back(str[i]);
    }

    bool reverse = false;

    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int ti;
        cin>>ti;
        if(ti==1){
            reverse = !reverse;
            continue;
        }
        int fi; char ci;
        cin>>fi>>ci;
        if(fi==1){
            if(reverse){
                ret.push_back(ci);
            }
            else{
                ret[start]=ci;
                start--;
            }
        }
        else{
            if(reverse){
                ret[start]=ci;
                start--;
            }
            else{
                ret.push_back(ci);
            }
        }
    }

    if(reverse){
        for(int i=ret.size()-1;i>start;i--){
            cout<<ret[i];
        }
        cout<<endl;
    }
    else{
        for(int i=start+1;i<ret.size();i++){
            cout<<ret[i];
        }
        cout<<endl;
    }
    return 0;
}

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

int n,pos;
vector<int> pre, in, post;

void rec(int l, int r){
  if(l >= r) return;
     int root = pre[pos++];
     int m = distance(in.begin(), find(in.begin(), in.end(), root));
     rec(l,m);
     rec(m + 1,r);
     post.push_back(root);
}

void solve(){
  pos = 0;
  rec(0, pre.size());
  for(int i = 0 ; i < n ; i++){
    if(i) cout << " ";
    cout << post[i];
  }
  cout << endl;
}

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

  for(int i = 0 ; i < n ; i++){
    cin >> k;
    pre.push_back(k);
  }

  for(int i = 0 ; i < n ; i++){
    cin >> k;
    in.push_back(k);
  }

  solve();

  return 0;
}
     



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

int main() {
    int a, b, i, j;
    cin >> a >> b;
    while (a !=0 && b != 0) {
        for (i = 0; i < a; i++){
            for(j = 0; j < b ; j++)
            if ((i + j) % 2 == 0)
                cout << "#";
            else cout << ".";    
            cout << endl;
        }
    cout << endl;    
    cin >> a >> b;    
    }
    return 0;
}


Measured memory_bytes: 3084
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def LF(): return list(map(float,sys.stdin.readline().rstrip().split()))

A,B = LF()
A = int(A)
B = int(B*100)
print(int(A*B/100))

Measured memory_bytes: 27180
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}

import Control.Applicative
import Control.Monad
import Control.Arrow
import Data.List
import Data.Maybe
import Data.Char
import qualified Data.ByteString.Char8 as B
import Text.Printf

readInt = ( readLn :: IO Int )
readInts = map ( read :: String -> Int ) . words <$> getLine

getList = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = do
	n <- readInt
	[ d, x ] <- readInts
	as <- replicateM n readInt
	print $ ( x + ) $ sum $ map ( solve d 1 ) as

solve d c a
	| c <= d = 1 + solve d ( c + a ) a
	| otherwise = 0

Measured memory_bytes: 1020
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();

        if (input.matches("keyence.*")) {System.out.println("YES"); return;}
        if (input.matches("keyenc.*e")) {System.out.println("YES"); return;}
        if (input.matches("keyen.*ce")) {System.out.println("YES"); return;}
        if (input.matches("keye.*nce")) {System.out.println("YES"); return;}
        if (input.matches("key.*ence")) {System.out.println("YES"); return;}
        if (input.matches("ke.*yence")) {System.out.println("YES"); return;}
        if (input.matches("k.*eyence")) {System.out.println("YES"); return;}
        if (input.matches(".*keyence")) {System.out.println("YES"); return;}

        System.out.println("NO");
    }
}

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

int main() {

    int n;

    cin >> n;

    int t[n],x[n],y[n];

    for(int i=0; i<n; i++){
        cin >> t[i] >> x[i] >> y[i];
    }

    int now_x,now_y,now_t;

    now_x = now_y = now_t = 0;

    string ans = "Yes";

    for(int i=0; i<n; i++){
        int diff_x,diff_y;

        diff_x = x[i] - now_x;
        diff_y = y[i] - now_y;

        if(diff_x < 0){
            diff_x *= -1;
        }

        if(diff_y < 0){
            diff_y *= -1;
        }

        if(t[i] - now_t < diff_x + diff_y){ //時間が足りなくて移動が不可能なら
            ans = "No";
            break;
        }

        if( (diff_x + diff_y + t[i] - now_t) % 2 == 1){ //時間が足りていても止まれないために移動が不可能ならば
            ans = "No";
            break;
        }

        now_x = x[i];
        now_y = y[i];
        now_t = t[i];

    }

    cout << ans << endl;

    return 0;
}

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

int main() {
  int N;
  cin>>N;
  vector<int> a(N);
  for(int j=0;j<N;j++){
    cin>>a[j];
  }
  int c=0;
  for(int i=0;i<N;i++){
    if (a[i]==0) continue;
    while(a[i]>0){
    int range=0;
    for(int j=i;j<N;j++){
      if(a[j]>0){
        range = j;
      }
      else if(a[j]<=0){
        break;
      }
    }
    for(int j=i;j<=range;j++){
      a[j] --;
    }
    c ++ ;
  }
  }
cout << c<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define eps 1e-9
#define MOD 1000000007;
#define INV_10 299473306;
using namespace std;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	long long x, nb=0;
	cin >> x;
	if(x==2)
	{
		cout << "1\n";
		return 0;
	}
	vector<long long>div;
	for(long long i = 2; i <= (int)(sqrt((long double)(x))); i++)
	{
		if(x%i==0)
		{
			div.push_back(i);
			if(i!=x/i)
				div.push_back(x/i);
		}
	}
	nb++;
	for(int i = 0; i < div.size(); i++)
	{
		long long cu=x;
		while(cu%div[i]==0)
			cu/=div[i];
		cu%=div[i];
		if(cu==1)
			nb++;
	}
	nb++;
	for(int i = 2; i <= (int)(sqrt((long double)(x-1))); i++)
	{
		if((x-1)%i==0)
		{
			nb++;
			if(i!=(x-1)/i)
				nb++;
		}
	}
	cout << nb << '\n';
}

Measured memory_bytes: 384
import bisect
from collections import deque
N = int(input())
A = deque([])
for i in range(N):
  A.append(int(input()))

dp = deque([])
l = len(A)
for i,a in enumerate(A):
  pos = bisect.bisect_left(dp, a)-1
  if pos<0:
    dp.appendleft(a)
  else:
    dp[pos] = a

print(len(dp))

Measured memory_bytes: 79272
#include <bits/stdc++.h>
using namespace std;
  
int main(){
    int x,y,g;
    cin >> x >>y >>g;

    if (x<y && y<g){
        cout<<x<<" "<<y<<" "<<g<<endl;
        return 0;
    }
    if (x<y && x>g){
        cout<<g<<" "<<x<<" "<<y<<endl;
        return 0;
    }
    if (x<g && g<y){
        cout<<x<<" "<<g<<" "<<y<<endl;
        return 0;
    }
    if (y<x && x<g){
        cout<<y<<" "<<x<<" "<<g<<endl;
        return 0;
    }
    if (g<y && y<x){
        cout<<g<<" "<<y<<" "<<x<<endl;
        return 0;
    }
    if (y<g && g<x){
        cout<<y<<" "<<g<<" "<<x<<endl;
        return 0;
    }
    if (y==g && g<x){
        cout<<y<<" "<<g<<" "<<x<<endl;
        return 0;
    }
    if (y<g && g==x){
        cout<<y<<" "<<g<<" "<<x<<endl;
        return 0;
    }
    if (y>g && g==x){
        cout<<x<<" "<<g<<" "<<y<<endl;
        return 0;
    }
    if (y==g && g>x){
        cout<<x<<" "<<g<<" "<<y<<endl;
        return 0;
    }
    if (y==x && g<x){
        cout<<g<<" "<<y<<" "<<x<<endl;
        return 0;
    }
    if (y==x && g>x){
        cout<<y<<" "<<x<<" "<<g<<endl;
        return 0;
    }
    if (y==g && g==x){
        cout<<y<<" "<<g<<" "<<x<<endl;
        return 0;
    }

} 


Measured memory_bytes: 3088
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#define range(i, r) for(int i=0;i<r;i++)
#define ranges(i, l, r) for(int i=l;i<r;i++)
typedef long long int ll;
using namespace std;

int main(int argc, char const *argv[]) {
  int N;
  std::cin >> N;
  std::vector<int> a(N), b(N), c(N);
  std::vector<std::vector<int> > DP(N + 1, std::vector<int> (3, 0));
  DP[0][0] = DP[0][1] = DP[0][2] = 0;
  ranges(i, 1, N + 1){
    std::cin >> a[i - 1] >> b[i-1] >> c[i-1];
    DP[i][0] = max(DP[i - 1][1], DP[i - 1][2]) + a[i-1];
    DP[i][1] = max(DP[i - 1][0], DP[i - 1][2]) + b[i-1];
    DP[i][2] = max(DP[i - 1][0], DP[i - 1][1]) + c[i-1];
  }
  cout << std::max({DP[N][0],DP[N][1],DP[N][2]}) <<'\n' ;
  return 0;
}


Measured memory_bytes: 6912
def resolve():
    R, G, B, n = map(int, input().split())
    ans = 0
    for r in range(n + 1):
        for g in range(n + 1):
            b = n - r * R - g * G
            if b >= 0 and b % B == 0:
                ans += 1
    print(ans)


if __name__ == "__main__":
    resolve()



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

typedef long long ll;

int main() {
    int N, L, s = 0, x = 1e9;
    cin >> N >> L;
    rep(i, N) {
        s += L + i;
        if (abs(L + i) < abs(x)) x = L + i; 
    }
    cout << s - x << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define Y first
#define X second
#define INF 1 << 30

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

bool cmp(const pi &a, const pi &b){
  int adis = a.Y*a.Y+a.X*a.X, bdis = b.Y*b.Y+b.X*b.X;
  if(adis != bdis) return adis > bdis;
  return a.X > b.X;
}


int main(){
  int N, dx, dy;
  scanf("%d", &N);
  while(N--){
    int x = 0, y = 0;
    vector<pi>rank;
    while(scanf("%d%d", &dx, &dy) && dx+dy){
      x += dx, y += dy;
      rank.push_back(make_pair(y, x));
    }
    //    rep(i, rank.size()) printf("%d %d\n", rank[i].Y, rank[i].X);

    sort(rank.begin(), rank.end(), cmp);
    printf("%d %d\n", rank[0].X, rank[0].Y);
  }
  return 0;
}

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

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,a,n) for(int i=a;i<n;i++)
#define mp(i,j) make_pair(i,j)
#define debug_v(v,N) for(int i=0;i<N;i++) { cout << v[i] << " "; } cout << endl;
#define debug_vv(v,H,W) for(int i=0;i<H;i++) { for(int j=0;j<W;j++) { cout << v[i][j] << " "; } cout << endl; }

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

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

void Main()
{
	int A, B, C; cin >> A >> B >> C;
	int res = (C - (A - B));
	cout << (res <= 0 ? 0 : res) << endl;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;


int main(){
  int N, K;
  cin >> N >> K;
  vector<int> v;
  rep(i,N){
    int a;
    cin >> a;
    v.push_back(a);
  }

  vector<double> w(N);
  rep(i,N){
    w[i] = (v[i]+1)/2.0;
  }

  double sum = 0;
  rep(i,K) sum += w[i];

  double ret = sum;
  REP(i,K,N){
    sum += w[i];
    sum -= w[i-K];

    ret = max(ret, sum);
  }

  printf("%.12lf\n", ret);
  
  return 0;
}


Measured memory_bytes: 5832
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

# include <stdio.h>
# include <bits/stdc++.h>


#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

using namespace __gnu_pbds;
using namespace std;
 
typedef
tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;

inline bool isvowel (char c) {
	c = tolower(c);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
    return 0;
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
ll a[N], res, pref[N];
pair < int, int > b[N];

int main () {
	SpeedForce;
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}

	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i ++) pref[i] = pref[i - 1] + a[i];
	res = pref[n];
	for (int i = 1;i <= m; i ++) {
		cin >> b[i].S >> b[i].F;
	}
	sort(b + 1, b + m + 1);
	reverse(b + 1, b + m + 1);
	int r = 1;
	for (int i = 1; i <= n; i ++) {
		while (b[i].S > 0 && r <= n && a[r] <= b[i].F) {
			b[i].S --;
			res += b[i].F - a[r];
			r ++;
		}
	}
	cout << res;

	return Accepted;
}

// B...a

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

int main() {
    string s;
    cin >> s;
    string ans = "";
    rep(i, s.size()) {
        if (s[i] == 'B') ans.erase(max((int)ans.size() - 1, 0));
        else ans += s[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <numeric>
#include <iomanip>
#define fi first
#define se second
#define fcout(n) cout<<fixed<<setprecision((n))
#define cinl(str) getline(cin,(str))
using namespace std;
bool value(int y,int x,int R,int C){return 0<=y&&y<R&&0<=x&&x<C;}
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
double pie=acos(-1);
int INF=1000000007;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };


int main() {
	string a,b,c;
	int x='a'-'A';
	cin>>a>>b>>c;
	
	a[0]=a[0]-x;
	b[0]=b[0]-x;
	c[0]=c[0]-x;
	cout<<a[0]<<b[0]<<c[0]<<endl;
	//cout<<ans<<endl;
}

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

int main(){
    int N;
    cin >> N;
    priority_queue<double, vector<double>, greater<double>> que;
    for(int i = 0; i < N; i++){
        double v;
        cin >> v;
        que.push(v);
    }
    for(int i = 0; i < N - 1; i++){
        double a = que.top();
        que.pop();
        double b = que.top();
        que.pop();
        que.push((a + b) / 2);
    }
    cout << que.top() << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
b.append(0)

sum = 0
rest_hero = 0

for i in range(n+1):
    hero = b[i] + rest_hero
    if a[i] >= hero:
        sum += hero
        rest_hero = 0
    else:  # a[i] < hero
        sum += a[i]
        if a[i] > rest_hero:
            rest_hero = b[i] - (a[i] - rest_hero)
        else:
            rest_hero = b[i]

print(sum)


Measured memory_bytes: 19116
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = mod * mod/3;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second

void solve() {
	int n, m;
	while (cin >> n >> m, n) {
		vector<vector<ll>> dl(n), ds(n);
		rep(i, n) {
			dl[i].resize(n, INF);
			ds[i].resize(n, INF);
			dl[i][i] = ds[i][i] = 0;
		}
		rep(i, m) {
			int x, y;ll t; char s; cin >> x >> y >> t >> s; x--; y--;
			if (s == 'L') {
				dl[x][y] = dl[y][x] = min(dl[x][y], t);
			}
			else {
				ds[x][y] = ds[y][x] = min(ds[x][y], t);
			}
		}
		//WF
		rep(k, n) {
			rep(i, n) {
				rep(j, n) {
					dl[i][j] = min(dl[i][j], dl[i][k] + dl[k][j]);
					ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j]);
				}
			}
		}

		int r; cin >> r; vector<int> z(r);
		rep(i, r) {
			cin >> z[i]; z[i]--;
		}
		vector<ll> dp(n, INF);
		dp[z[0]] = 0;
		rep1(i, r - 1) {
			vector<ll> cop(n, INF);
			rep(j, n) {
				rep(k, n) {
					ll sum;
					if (j != k) {
						sum = dl[z[i - 1]][j] + ds[j][k] + dl[k][z[i]];
					}
					else {
						sum = dl[z[i - 1]][z[i]];
					}
					cop[k] = min(cop[k], sum + dp[j]);
				}
			}
			rep(j, n) {
				dp[j] = cop[j];
			}
		}
		ll ans = INF;
		rep(i, n) {
			ans = min(ans, dp[i]);
		}
		cout << ans << endl;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	//stop
	return 0;
}


Measured memory_bytes: 3364
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
using namespace std;
int ga,sa,ba,gb,sb,bb,i;
long long f[25000005],n;
int main()
{
	cin>>n;
	scanf("%d %d %d",&ga,&sa,&ba);
	scanf("%d %d %d",&gb,&sb,&bb);
	for(i=ga;i<=n;i++)
		f[i]=max(f[i],f[i-ga]+gb);
	for(i=sa;i<=n;i++)
		f[i]=max(f[i],f[i-sa]+sb);
	for(i=ba;i<=n;i++)
		f[i]=max(f[i],f[i-ba]+bb);
	long long nn=n;
	for(i=1;i<=nn;i++)
		n=max(n,nn+f[i]-i);
	memset(f,0,sizeof(f));
	for(i=gb;i<=n;i++)
		f[i]=max(f[i],f[i-gb]+ga);
	for(i=sb;i<=n;i++)
		f[i]=max(f[i],f[i-sb]+sa);
	for(i=bb;i<=n;i++)
		f[i]=max(f[i],f[i-bb]+ba);
	nn=n;
	for(i=1;i<=nn;i++)
		n=max(n,nn+f[i]-i);
	cout<<n<<endl;
}


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

int main(){
    string a,b,c;
    cin >> a >> b >> c;
    if(a[a.size()-1] == b[0] && b[b.size()-1] == c[0]) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}


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

int main(){
	int n,s=0,s2=0;scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int a;
		scanf("%d",&a);
		s2 -= a*a;
		s += a;
	}
	s2 += s * s;
	printf("%d\n",s2/2);
}

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

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORd(i, a, b) for (int i = (a) ; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define sp system("pause")
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;

void TimeExecution() {
    cout << "\n\n===>> Time Execution: " << clock() / (double)1000 << " sec(s).";
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    /*
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    */
    int n;
    cin >> n;
    cout << n * n;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<map>
#include<string>
#define Z(z)m[a+b]=1;m[b+a]=1;reverse(z.begin(),z.end());
using namespace std;main(){string s,a,b;for(cin>>s;cin>>s;){
map<string,int>m;
for(int i=0;++i<s.length();){a=s.substr(0,i),b=s.substr(i);Z(a)Z(b)Z(a)Z(b)}
cout<<m.size()<<endl;
}}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; string S; cin >> N >> S;
    vector<vector<int>> dp(N+1,vector<int>(3,-INF));
    dp[0][0]=0;
    int pre=0,suf;
    for (int i=0;i<N;++i){
        for (int j=0;j<3;++j) dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
        if (S[i]=='1') ++pre;
        else {
            for (suf=0;i+suf+1<N;++suf){
                if (S[i+suf+1]=='0') break;
            }
            dp[i+1][0]=max(dp[i+1][0],max(dp[i][1],dp[i][2]));
            if (suf>=1) dp[i+1][1]=max(dp[i+1][1],max(dp[i][0],dp[i][1]-1)+pre);
            if (pre>=1) dp[i+1][2]=max(dp[i+1][2],dp[i][0]+suf);
            if (pre>=2) dp[i+1][2]=max(dp[i+1][2],max(dp[i][1],dp[i][2]-1)+suf);
            pre=0;
        }
    }
    int ans=max({dp[N][0],dp[N][1],dp[N][2]});
    cout << ans << '\n';
}

Measured memory_bytes: 28188
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long int N, g[3], s[3], b[3];

long long int dp[5555];
long long int dp2[30000000];

int main(void) {

	cin >> N;

	for (int i = 1; i <= 2; i++) {
		cin >> g[i] >> s[i] >> b[i];
	}

	long long int M=0;

	for (int i = 1; i <= N; i++) {
		dp[i] = i;
		if (i - g[1] >= 0) {
			dp[i] = max(dp[i], dp[i - g[1]] + g[2]);
		}
		if (i - s[1] >= 0) {
			dp[i] = max(dp[i], dp[i - s[1]] + s[2]);
		}
		if (i - b[1] >= 0) {
			dp[i] = max(dp[i], dp[i - b[1]] + b[2]);
		}
		M = max(M, dp[i]);
	}

	//=============================
	long long int ans = 0;

	for (long long int i = 1; i <= M; i++) {
		dp2[i] = i;
		if (i - g[2] >= 0) {
			dp2[i] = max(dp2[i], dp2[i - g[2]] + g[1]);
		}
		if (i - s[2] >= 0) {
			dp2[i] = max(dp2[i], dp2[i - s[2]] + s[1]);
		}
		if (i - b[2] >= 0) {
			dp2[i] = max(dp2[i], dp2[i - b[2]] + b[1]);
		}

		ans = max(ans, dp2[i]);
	}

	cout << ans << endl;

	return 0;
}

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

int main(){
  char N[4];
  scanf("%s",N);
  for(int i=0;i<3;i++){
    if(N[i]=='1') N[i]='9';
    else if(N[i]=='9') N[i]='1';
  }
  printf("%s\n",N);
  return 0;
}

Measured memory_bytes: 1648
//17571@nith.ac.in @Ankit Verma
#include <bits/stdc++.h>
using namespace std;
#define ff          first
#define ss          second
#define pb          push_back
#define MP          make_pair
#define int         long long
#define ll          long long
#define inf         0x3f3f3f3f
#define MOD         2019
#define ld          long double
#define eb          emplace_back
#define pii         pair<int,int>
#define ull         unsigned long long
#define all(v)      v.begin(), v.end()
#define f(i,x,n)    for(int i=x;i<n;i++)
#define fr(i,x,n)   for(int i=x;i>=n;i--)
#define fastio      ios::sync_with_stdio(false)

void IO() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

int32_t main() {
    //IO();
    fastio;
    cin.tie(nullptr);
    cout.tie(nullptr);
    string s; cin >> s;
    int n = s.size();
    vector <int> cache(MOD);
    int suff = 0; int pow_of_ten = 1;
    cache[suff]++; int res = 0;
    for (int i = n - 1; i >= 0; i--) {
    	int digit = s[i] - '0';
    	suff = (suff + digit * pow_of_ten) % MOD;
    	pow_of_ten = pow_of_ten * 10 % MOD;
    	res += cache[suff];
    	cache[suff]++;
    }	
    cout << res << endl;
    

    return 0;
}

Measured memory_bytes: 3740
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

int R, G, B, N;
long long ans = 0;

int main(int argc, char *argv[])
{
  cin >> R >> G >> B >> N;

  for (int i = 0; R*i <=  N; i++) {
    if (R*i > N) continue;
    for (int j = 0; R*i + G*j <= N; j++) {
      if ((N - (R*i + G*j)) % B == 0)  ans++;
    }
  }

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[2010],b[2010],l[2010],r[2010],st[2010],mx[2010];
char s[2010];
int cmp(int x,int y){return r[x]<r[y];}
int main()
{
	scanf("%s\n",s+1);int n=strlen(s+1);
	for (int i=1;i<=n;i++) a[i]=s[i]-'0';
	scanf("%s",s+1);
	for (int i=1;i<=n;i++) b[i]=s[i]-'0';
	memset(l,127/10,sizeof(l));memset(r,127/10,sizeof(r));l[0]=r[0]=0;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++) if (b[j])
	{
		l[i]=min(l[i],(i-j+n)%n);
		r[i]=min(r[i],(j-i+n)%n);
	}
	int ans=2100000000;
	for (int i=1;i<=n;i++)
	{
		int top=0,now=i;
		for (int j=1;j<=n;j++)
		{
			if (a[now]!=b[j]) st[++top]=now;
			now=now%n+1;
		}
		sort(st+1,st+top+1,cmp);
		mx[top+1]=0;for (int j=top;j>=0;j--) mx[j]=max(mx[j+1],l[st[j]]);
		for (int j=0;j<=top;j++)
		{
			ans=min(ans,r[st[j]]*2+max((i-(n+1)+n)%n,mx[j+1])*2+top-(i-(n+1)+n)%n);
			ans=min(ans,mx[j+1]*2+max(((n+1)-i+n)%n,r[st[j]])*2+top-((n+1)-i+n)%n);
		}
	}
	if (ans>1e7) ans=-1;
	printf("%d\n",ans);
}

Measured memory_bytes: 384
N, M = map(int, input().split())
E = []
T = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    T[a].add(b)
    T[b].add(a)
    E.append([a, b])

ans = 0
for i in range(M):
    s, t  = E[i][0], E[i][1]
    V, queue = set([s]) | T[s] - set([t]), T[s] - set([t])
    Bridge = True
    while len(queue) > 0:
        v = queue.pop()
        for u in T[v]:
            if u == t:
                Bridge = False
                break
            if u not in V:
                queue.add(u)
                V.add(u)
        else:
            continue
        break
    if Bridge:
        ans += 1

print(ans)

Measured memory_bytes: 3064
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// Cosmic Market
// 2012/12/04
public class Main{
	Scanner sc=new Scanner(System.in);

	int r, c, q;
	int[] a, b, order;

	void run(){
		for(;;){
			r=sc.nextInt();
			c=sc.nextInt();
			q=sc.nextInt();
			if((r|c|q)==0){
				return;
			}
			a=new int[q];
			b=new int[q];
			order=new int[q];
			for(int i=0; i<q; i++){
				a[i]=sc.nextInt();
				b[i]=sc.nextInt();
				order[i]=sc.nextInt();
			}
			solve();
		}
	}

	void solve(){
		boolean[] row=new boolean[r];
		boolean[] col=new boolean[c];
		int nRow=0, nCol=0;
		int win=0, lose=0;
		for(int j=q-1; j>=0; j--){
			if(a[j]==0){
				if(row[b[j]]){
					continue;
				}
				row[b[j]]=true;
				if(order[j]==0){
					lose+=c-nCol;
				}else{
					win+=c-nCol;
				}
				nRow++;
			}else{
				if(col[b[j]]){
					continue;
				}
				col[b[j]]=true;
				if(order[j]==0){
					lose+=r-nRow;
				}else{
					win+=r-nRow;
				}
				nCol++;
			}
		}
		println(win+"");
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new Main().run();
	}
}

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

int main() {
  int n,l;cin >> n >> l;
  vector<string> a(n);
  rep(i,n)cin >> a.at(i);
  
  sort(a.begin(),a.end());
  rep(i,n)cout << a.at(i);
  cout << endl;
}

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

STDIN.gets.chomp.to_i
array = STDIN.gets.chomp.split(' ').map(&:to_i)

def get_answer(first, array)
  ans = 0
  sum = first
  array.each do |a|
    if sum * (sum + a) < 0 # sum と (sum + a)の符号が異なる場合
      sum += a
    else
      next_sum = sum < 0 ? 1 : -1
      ans += (next_sum - (sum + a)).abs
      sum = next_sum
    end
  end

  return ans
end

first = array.shift

if first == 0
  ans = [get_answer(1, array), get_answer(-1, array)].min + 1
else
  ans1 = get_answer(first, array)
  ans2 = get_answer((-1 * first/first.abs), array) + first.abs + 1
  ans = [ans1, ans2].min
end

puts ans


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


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

    int cnt = 0;
    rep(i,3){
        if(s[i] == t[i]) cnt++;
    }

    cout << cnt << endl;
}


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

int f(int n, int m) {
  n %= m;
  while (n < 0) n += m;
  int ret = 1;
  while (n) n = n % __builtin_popcount(n), ret++;
  return ret;
}

int main() {
  int N;
  string S;
  cin >> N >> S;
  int cnt = count(S.begin(), S.end(), '1');
  int mod1 = max(1, cnt - 1);
  int mod2 = cnt + 1;
  vector<int> V1(N), V2(N), X(N), Y(N);
  int acc1 = 0, acc2 = 0;
  for (int i = N - 1, now1 = 1, now2 = 1; i >= 0; i--, (now1 *= 2) %= mod1, (now2 *= 2) %= mod2) {
    (acc1 += (V1.at(i) = (S.at(i) - '0') * now1) %= mod1) %= mod1;
    (acc2 += (V2.at(i) = (S.at(i) - '0') * now2) %= mod2) %= mod2;
    X.at(i) = now1 % mod1;
    Y.at(i) = now2 % mod2;
  }
  for (int i = 0; i < N; i++) {
    int ans;
    if (S.at(i) == '1' && cnt == 1) ans = 0;
    else if (S.at(i) == '1') ans = f(acc1 - X.at(i), mod1);
    else ans = f(acc2 + Y.at(i), mod2);
    cout << ans << "\n";
  }
}

Measured memory_bytes: 6728