akhauriyash/Code-Regression huggingface dataset:
import java.util.Iterator;
import java.util.PrimitiveIterator;
import java.util.Scanner;
import java.util.function.Supplier;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Main{
	static Scanner s=new Scanner(System.in);

	void solve(){
		System.out.println(gInt()<=8&&gInt()<=8?"Yay!":":(");
	}
	
	public static void main(String[] A){
		new Main().solve();
	}

	static int gInt(){
		return Integer.parseInt(s.next());
	}
	static long gLong(){
		return Long.parseLong(s.next());
	}
	static double gDouble(){
		return Double.parseDouble(s.next());
	}

	SupplyingIterator<Integer> ints(int n){
		return new SupplyingIterator<>(n,Main::gInt);
	}
	SupplyingIterator<Long> longs(int n){
		return new SupplyingIterator<>(n,Main::gLong);
	}
	SupplyingIterator<Double> doubles(int n){
		return new SupplyingIterator<>(n,Main::gDouble);
	}
	SupplyingIterator<String> strs(int n){
		return new SupplyingIterator<>(n,s::next);
	}

	Range rep(int i){
		return Range.rep(i);
	}
	Range rep(int f,int t,int d){
		return Range.rep(f,t,d);
	}
	Range rep(int f,int t){
		return rep(f,t,1);
	}
	Range rrep(int f,int t){
		return rep(t,f,-1);
	}

	IntStream REP(int v){
		return IntStream.range(0,v);
	}
	IntStream REP(int l,int r){
		return IntStream.rangeClosed(l,r);
	}

	IntStream INTS(int n){
		return IntStream.generate(Main::gInt).limit(n);
	}
	Stream<String> STRS(int n){
		return Stream.generate(s::next).limit(n);
	}

}
class SupplyingIterator<T> implements Iterable<T>,Iterator<T>{
	int			t;
	Supplier<T>	supplier;

	SupplyingIterator(int t,Supplier<T> supplier){
		this.t=t;
		this.supplier=supplier;
	}

	@Override
	public Iterator<T> iterator(){
		return this;
	}

	@Override
	public boolean hasNext(){
		return t>0;
	}

	@Override
	public T next(){
		--t;
		return supplier.get();
	}

}
class Range implements Iterable<Integer>,PrimitiveIterator.OfInt{
	int to,cur,d;

	Range(int from,int to,int d){
		this.cur=from-d;
		this.to=to;
		this.d=d;
	}

	Range(int n){
		this(0,n-1,1);
	}

	@Override
	public Iterator<Integer> iterator(){
		return this;
	}

	@Override
	public boolean hasNext(){
		return cur+d==to||(cur!=to&&(cur<to==cur+d<to));
	}

	@Override
	public int nextInt(){
		return cur+=d;
	}

	static Range rep(int i){
		return new Range(i);
	}
	static Range rep(int f,int t,int d){
		return new Range(f,t,d);
	}
	static Range rep(int f,int t){
		return rep(f,t,1);
	}
	static Range rrep(int f,int t){
		return rep(f,t,-1);
	}

}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#include <iterator>
#include <tuple>
using namespace std;
using ll = long long;

int main()
{
  int r;
  cin >> r;
  if (r < 1200)
    cout << "ABC" << endl;
  else if (r < 2800)
    cout << "ARC" << endl;
  else
    cout << "AGC" << endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define       inf                  1<<30
#define       p5                   100007
#define       p6                   1000007
#define       PI                   acos(-1)
#define       M                    1000000007
#define       sc                   scanf
#define       ss                   second
#define       ff                   first
#define       pf                   printf
#define       scin(x)              sc("%d",&(x))
#define       scin2(x,y)            sc("d",&(x),&(y))
#define       READ(f)              freopen(f, "r", stdin)
#define       WRITE(f)             freopen(f, "w", stdout)
#define       ll                   long long
#define       ull                  unsigned long long
#define       pii                  pair < int, int>
#define       pp                  pair < ll, ll>
#define       pq                   priority_queue
#define       pb                   push_back
#define       FastRead             ios_base::sync_with_stdio(0);cin.tie(0)
//int month[]={31,28,31,30,31,30,31,31,30,31,30,31};
//int dx[5] = {1, -1, 0, 0 };
//int dy[5] = {0, 0, 1, -1};
using namespace std;
int ar[1005][1005];
char grd[1005][1005];
int main()
{
	int n,i,j,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
        sc("%s",grd[i]);
	}
	/*for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<grd[i][j];
        }
        cout<<endl;
	}*/
	ar[1][1]=1;
	for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
           if(grd[i-1][j-1]=='.'){
            ar[i][j]=(ar[i][j]+ar[i-1][j]+ar[i][j-1])%M;
           }
        }
	}
	/*for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            cout<<ar[i][j]<<" ";
        }
        cout<<endl;
	}*/
	cout<<ar[n][m]<<endl;
	return 0;
}
//C%sE91971@%#@
//ssl%honeypod%
//https://prosenc.blogspot.com/2016/



Measured memory_bytes: 5120
#include<iostream>
#include<cstring> 
#include<cmath>
using namespace std;
int main()
{
	int a[3][105];
	int dp[3][105];
	int n;
	cin>>n;
	memset(a,0,sizeof(a));
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=2;i++)
	{
		for(int j=1;j<=n;j++)
		cin>>a[i][j]; 
	}
	dp[1][1]=a[1][1];
	for(int i=1;i<=2;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i==1)dp[i][j]=dp[i][j-1]+a[i][j];
			else dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
		}
	}
	cout<<dp[2][n];
	return 0;
} 

Measured memory_bytes: 256
from collections import deque
x = input()
stack = deque(x[0])
for i in range(1,len(x)):
    if x[i] == "S":
        stack.appendleft(x[i])
    else: #x[i] == "T"
        if len(stack) == 0:
            stack.append(x[i])
        elif stack[0] == "T":
            stack.appendleft(x[i])
        else:
            stack.popleft()
print(len(stack))

Measured memory_bytes: 10820
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

int main() {
    ll N, K;
    cin >> N >> K;

    vec<ll> P(N);
    rep(i, N) cin >> P[i], --P[i];

    vec<ll> C(N);
    rep(i, N) cin >> C[i];

    ll ans = -1e18 - 9;
    rep(i, N) {
        ll now = i;
        ll smS = 0;
        vec<ll> t;
        while (1) {
            smS += C[now];
            t.push_back(smS);
            now = P[now];
            if (now == i) break;
        }
        int L = t.size();
        rep(j, L) {
            ll tmp     = -1e18 - 9;
            ll zan     = K - (j + 1);
            if(zan < 0) break;
            ll roopCnt = zan / L;
            ll roopSm  = smS * roopCnt;
            tmp        = max({tmp, t[j], t[j] + roopSm});
            ans        = max(ans, tmp);
        }
    }
    cout << ans << '\n';
}


Measured memory_bytes: 3784
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;
#define INF 100000000
#define MOD 1000000007

int main()
{
	const int N = 2000;
	int n;
	ll x, y, score;
	ll a[N + 1];

	// Xさん、Yさんが持っているカードの数字をそれぞれx、yとする
	cin >> n >> x >> y;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	// ゲームが終了する時点でXさんかYさんのどちらかのカードは必ずn枚目のカードである
	// Xさんがn枚目のカードを持って終了する場合(自分が全部引く)と
	// Yさんがn枚目のカードを持って終了する場合(自分が(n-1)枚目まで引く)を比較して
	// 大きいスコアを出力してみる
	// まず自分が全部引く場合
	x = a[n];
	score = llabs(x - y);
	// 相手に最後を引かせる場合
	if (n > 1) { // n = 1ならXさんが1枚引いて終了のため
		x = a[n - 1];
		y = a[n];
		if (score < llabs(x - y)) {
			score = llabs(x - y);
		}
	}
	cout << score << endl;

	return (0);
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

//Util
func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func maxInt(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func minInt(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func absInt(a int) int {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

//Main
var sc = bufio.NewScanner(os.Stdin)
var n int
var s string

func main() {
	sc.Split(bufio.ScanWords)
	n = nextInt()
	m := make(map[string]int, n)
	for i := 0; i < n; i++ {
		s = nextStr()
		if _, ok := m[s]; ok {
			m[s]++
		} else {
			m[s] = 1
		}
	}
	//fmt.Println(m)
	fmt.Println(len(m))
}


Measured memory_bytes: 13064
#include<stdio.h>
int main()
{
    int a[9],s,i,n,m,t;
    while(~scanf("%d",&n))
    {
        s=0;
        t=1;
        for(i=0;i<=8;i++)
            a[i]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&m);
            if(m<=399)
                a[0]++;
            else if(m<=799)
                a[1]++;
            else if(m<=1199)
                a[2]++;
            else if(m<=1599)
                a[3]++;
            else if(m<=1999)
                a[4]++;
            else if(m<=2399)
                a[5]++;
            else if(m<=2799)
                a[6]++;
            else if(m<=3199)
                a[7]++;
            else
                a[8]++;
        }
        for(i=0;i<=7;i++)
            if(a[i]>=1)
                s++;
                
            if(s!=0)
            t=s;
            s=s+a[8];
            printf("%d %d\n",t,s);
    }
    return 0;
}

Measured memory_bytes: 128
#include <cstdio>
int main(){
	int x1, y1, x2, y2;
	scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
	int x = x1 - x2, y = y1 - y2;
	printf("%d %d %d %d",x2 + y,y2 - x,x1 + y,y1 - x);
}

Measured memory_bytes: 128
import sys
from io import StringIO
import unittest
import os
import copy

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


def count(target_list: list, target_str: str):
    cnt = 0
    for target in target_list:
        cnt += target.count(target_str)
    return cnt


# 実装を行う関数
def resolve(test_def_name=""):
    h, w, k = map(int, input().split())
    data = [list(list(input())) for i in range(h)]

    ans = 0
    for i in range(1 << (h + w)):
        table = copy.deepcopy(data)
        for j in range(h):
            if i & 1 << j:
                table[j] = ["." for aaaa in range(w)]

        for jj in range(w):
            target = j + jj + 1
            if i & 1 << target:
                for aaaa in table:
                    aaaa[jj] = "."

        if count(table, "#") == k:
            ans += 1

    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """2 3 2
..#
###"""
        output = """5"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """2 3 4
..#
###"""
        output = """1"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """2 2 3
##
##"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """6 6 8
..##..
.#..#.
#....#
######
#....#
#....#"""
        output = """208"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()


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

const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

int n;
ll a[200000];

int main() {
    cin >> n;
    rep(i,n) {
        cin >> a[i];
        a[i] -= i+1;
    }
    sort(a,a+n);
    ll x = a[n/2];
    ll ans = 0;
    rep(i,n) {
        ans += abs(a[i]-x);
    }
    cout << ans << endl;
}
































Measured memory_bytes: 1792
#include<bits/stdc++.h>
    using namespace std;
    using Int = long long;
    template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
    template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
     
    //INSERT ABOVE HERE
    signed main(){
      Int n;
      cin>>n;
      vector<Int> xs(n),ys(n);
      for(Int i=0;i<n;i++) cin>>xs[i]>>ys[i];
     
      using D = double;
      D ans=0;
      for(Int i=0;i<n;i++){
        Int gx=xs[i],gy=ys[i];
        for(Int k=0;k<4;k++){
          {
            Int nx=-gy,ny=gx;
            gx=nx;
            gy=ny;
          }
     
          Int sx=0,sy=0;
          Int px=0,py=0;
          Int qx=0,qy=0;
     
          auto dot=[&](Int x1,Int y1,Int x2,Int y2){return x1*x2+y1*y2;};
          auto cross=[&](Int x1,Int y1,Int x2,Int y2){return x1*y2-x2*y1;};
          for(Int j=0;j<n;j++){
            Int res=dot(xs[j],ys[j],gx,gy);
            if(res<0) continue;
            if(res>0){
              sx+=xs[j];
              sy+=ys[j];
              continue;
            }
            if(cross(xs[j],ys[j],gx,gy)>0){
              px+=xs[j];
              py+=ys[j];
            }else{
              qx+=xs[j];
              qy+=ys[j];
            }
          }
     
          for(Int t=0;t<4;t++){
            D bx=sx,by=sy;
            if(t&1) bx+=px,by+=py;
            if(t&2) bx+=qx,by+=qy;
            chmax(ans,bx*bx+by*by);
          }
        }
      }
     
      cout<<fixed<<setprecision(12)<<sqrt(ans)<<endl;
      return 0;
    }

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

int main(){
    int a, b;
    cin >> a >> b;
    if(a > 12){
        cout << b;
    }else if(a < 6){
        cout << 0;
    }else{
        cout << b/2;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>       // for next_permutation
#include <vector>
#include <bits/stl_numeric.h>
#include <queue>

#define DEBUG 0
#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;

static const int MAX = 510000;

ll euclidean_gcd(ll a, ll b) {
  if(a < b) return euclidean_gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b; //あまりが0ならそれが、最大公約数
}

int main() {
    ll k,res;
    cin >> k;
    res = 0;

    for(int a = 1; a <= k; ++a)
    {
        for(int b = 1; b <= k; ++b)
        {
            for(int c = 1; c <= k; ++c)
            {
                ll tmp;
                tmp = euclidean_gcd(a,b);
                tmp = euclidean_gcd(tmp,c);
                res += tmp;
            }
        }
    }

    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3632
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (ll ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 1000000000000000000ll
#define N 100010
ll g[N],size,dis[N],ans,S,T,maxx[N],n,i,o,p,flag,anss,l,r,a,b;
struct node {ll to,next;}e[N];
void add(ll o,ll p){e[++size].to=p;e[size].next=g[o];g[o]=size;}
void dfs1(ll x,ll fa)
{
	ll ch=0;
	for (ll k=g[x];k;k=e[k].next)
	{
		ll y=e[k].to;
		if (y!=fa&&y!=l&&y!=r) 
		{
			dis[y]=dis[x]+1;
			dfs1(y,x);
			ch++;
		}
	}
	maxx[dis[x]]=max(maxx[dis[x]],ch);
}
void find(ll x,ll fa)
{
	if (x==T) 
	{
		flag=1;if (ans%2==0) {if (dis[x]==ans/2) {if (a==0) a=x;else b=x;}}
		else if (dis[x]==ans/2||dis[x]==(ans+1)/2){ if (a==0) a=x;else b=x;}
		return ;
	}
	for (ll k=g[x];k;k=e[k].next)
	{
		ll y=e[k].to;
		if (y!=fa)
		{
			find(y,x);
			if (flag==1)
			{
				if (ans%2==0) {if (dis[x]==ans/2) {if (a==0) a=x;else b=x;}}
				else if (dis[x]==ans/2||dis[x]==(ans+1)/2){ if (a==0) a=x;else b=x;}
				return ;
			}
		}
	}
}
void dfs(ll x,ll fa)
{
	for(ll k=g[x];k;k=e[k].next)
	{
		ll y=e[k].to;
		if (y!=fa)
		{
			dis[y]=dis[x]+1;
			dfs(y,x);
		}
	}
}
void solve(ll x,ll y)
{
//	pr(x),pr(y);
	l=x,r=y;
	for (i=0;i<=n;i++) maxx[i]=1;
	dis[x]=0,dis[y]=0;dfs1(x,-1);dfs1(y,-1);
	ll ret=2;
	for (i=0;i<=n;i++) ret*=maxx[i];
//	pri(maxx,n);
//	pr(ret);
	anss=min(anss,ret);
//	cout<<endl;
}
int main()
{	
	scanf("%lld",&n);
	for (i=1;i<n;i++)
	{
		scanf("%lld %lld",&o,&p);
		add(o,p);add(p,o);
	}
	dfs(1,-1);
	S=max_element(dis+1,dis+1+n)-dis;
	dis[S]=0;
	dfs(S,-1);
	T=max_element(dis+1,dis+1+n)-dis;
	ans=dis[T];
	printf("%lld ",(ans+2)/2);
	flag=0;
	anss=inf;
	find(S,-1);
	
	//pr(a),pr(b);
	if (b) solve(a,b);
	else
	{
		for (i=0;i<=n;i++) maxx[i]=1;
		dis[a]=0;dfs1(a,-1);
		ll ret=1;
		for (ll i=0;i<=n;i++) ret*=maxx[i];
		anss=min(anss,ret);
		
		for (ll k=g[a];k;k=e[k].next)
		solve(a,e[k].to);
	}
	printf("%lld\n",anss);
}

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

bool rk(string t, string p) {
	int  k=1000007, m=1000000007;
	long long ht = 0;
	long long  po = 1;
	for (int i = 0; i < p.size();i++) {
		po *= k;
		po %= m;
	}
	po %= m;
	for (int i = 0; i < p.size();i++) {
		ht *= k;
		ht += t[i];
		ht %= m;
	}
	long long hp = 0;
	for (int i = 0; i < p.size(); i++) {
		hp *= k;
		hp += p[i];
		hp %= m;
	}
	for (int i = 0; i < t.size()-p.size()+1;i++) {
		if (hp==ht) {
			if (t.substr(i,p.size())==p) {
				return true;
			}
		}
		if (i+p.size()<t.size()) {
			ht *= k;
			ht -= t[i] * po;
			ht += t[i + p.size()];
			ht %= m;
			if (ht < 0) {
				ht += m;
			}
		}
	}
	return false;
}

bool calc(string s,int n) {
	if (n==0) {
		return true;
	}
	for (int i = 0; i+n*2 <= s.size();i++) {
		string ss1 = s.substr(i, n);
		string ss2 = s.substr(i+n);
		if (rk(ss2, ss1)) {
			return true;
		}
		
	}
	return false;
	
}

int main() {
	int n;
	string s;
	cin >> n;
	cin >> s;
	int left = 0;
	int right = n/2+1;
	while (left < right) {
		int i = left + (right - left) / 2;
		if (calc(s, i)) {
			left = i + 1;
		}
		else {
			right = i;
		}
	}
	cout << left-1 << endl;
}


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

int main() {
  int a,b,k;cin>>a>>b>>k;
  if(b-a+1>=2*k){
    for(int i=a;i<a+k;i++)cout<<i<<endl;
    for(int i=b-k+1;i<=b;i++)cout<<i<<endl;
  }
  else {
    for(int i=a;i<=b;i++)cout<<i<<endl;
  }
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll GCD(ll a, ll b){ return a ? GCD(b % a, a) : b; }
int main(){
    double a,b,h,m;
    cin>>a>>b>>h>>m;
    double rad = abs(((h*60+m)*0.5)-(m*6));
    rad *= 3.14159265359/180;
    cout<<fixed<<setprecision(11)<<sqrt(pow(a,2)+pow(b,2)-2*a*b*cos(rad))<<endl;
}

Measured memory_bytes: 4228
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
s = input()
v = 0
l = [[s[0],1]]
for c in s[1:]:
    if l[-1][0]!=c:
        l.append([c,1])
    else:
        l[-1][1] += 1
vs = []
if len(l)==1:
    ans = n-1
else:
    num = 0
    for i in range(n):
        if (i==0 and s[i]=="L") or (i==n-1 and s[i]=="R") or (0<=i<=n-2 and s[i]=="R" and s[i+1]=="L") or (1<=i and s[i]=="L" and s[i-1]=="R"):
            num += 1
    vals = []
    for i in range(len(l)):
        if l[i][0]=="L":
            if i in (0, len(l)-1):
                vals.append(1)
            else:
                vals.append(2)
    vals.sort()
    ans = n - (num - sum(vals[-k:]))
    
    vals = []
    for i in range(len(l)):
        if l[i][0]=="R":
            if i in (0, len(l)-1):
                vals.append(1)
            else:
                vals.append(2)
    vals.sort()
    ans = max(ans, n - (num - sum(vals[-k:])))
    
print(ans)

Measured memory_bytes: 90516
// AOJ 2153: Mirror Cave
// 2017.11.11 bal4u@uu

#include <stdio.h>
#include <string.h>
#define TM 0
#if TM
#include <time.h>
#endif

#define QMAX 150000
typedef struct { char lr, lc, rr, rc; } Q;
Q q[QMAX+2]; int top, end;

char ml[52][52], mr[52][52];
char mk[52][52][52][52];
int mvl[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int mvr[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};

int main()
{
	int w, h, r, c, lr, lc, rr, rc, lr2, lc2, rr2, rc2, i, f;
	int slr, slc, srr, src, ans;
#if TM
	clock_t start, end;
	start = clock();
#endif
	for (r = 0; r <= 51; r++) ml[r][0] = mr[r][0] = '#';
	for (c = 0; c <= 51; c++) ml[0][c] = mr[0][c] = '#';

	while (scanf("%d%d", &w, &h) && w > 0) {
		for (f = 0, r = 1; r <= h; r++) {
			scanf("%s%s", ml[r]+1, mr[r]+1);
			if (f < 3) for (c = 1; c <= w; c++) {
				if (ml[r][c] == 'L') slr = r, slc = c, f |= 1;
				if (mr[r][c] == 'R') srr = r, src = c, f |= 2;
			}
		}
		for (r = 1; r <= h; r++) ml[r][w+1] = mr[r][w+1] = '#';
		for (c = 1; c <= w; c++) ml[h+1][c] = mr[h+1][c] = '#';

		memset(mk, 0, sizeof(mk));
		q[0].lr = slr, q[0].lc = slc, q[0].rr = srr, q[0].rc = src, top = 0, end = 1;
		mk[slr][slc][srr][src] = 1;
		ans = 0;
		while (top != end) {
			lr = q[top].lr, lc = q[top].lc, rr = q[top].rr, rc = q[top].rc;
			if (++top == QMAX) top = 0;
			if (ml[lr][lc] == '%' && mr[rr][rc] == '%') { ans = 1; break; }
			if (ml[lr][lc] == '%' || mr[rr][rc] == '%') continue;

			for (i = 0; i < 4; i++) {
				lr2 = lr + mvl[i][0], lc2 = lc + mvl[i][1];
				rr2 = rr + mvr[i][0], rc2 = rc + mvr[i][1];
				if (ml[lr2][lc2] == '#') lr2 = lr, lc2 = lc;
				if (mr[rr2][rc2] == '#') rr2 = rr, rc2 = rc;
				if (mk[lr2][lc2][rr2][rc2]) continue;
				mk[lr2][lc2][rr2][rc2] = 1;
				q[end].lr = lr2, q[end].lc = lc2, q[end].rr = rr2, q[end].rc = rc2;
				if (++end == QMAX) end = 0;
			}
		}
		puts(ans ? "Yes" : "No");
	}
#if TM
	end = clock();
	printf("time %lf\n", (double)(end-start)/CLOCKS_PER_SEC);
#endif
	return 0;
}

Measured memory_bytes: 9396
from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = deque()
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat.append((h, w, 0))
    dp[h] = s

while len(mat):
    h, w, cnt = mat.popleft()

    for t, h, w, cnt in ((h > 0, h - 1, w, cnt),(h < H-1, h + 1, w, cnt),(w > 0, h , w - 1, cnt),(w < W-1, h , w + 1, cnt)):
        if t and dp[h][w] == ".":
            mat.append((h, w, cnt+1))
            dp[h][w] = "#"

print(cnt)


Measured memory_bytes: 153308
import java.util.*;
import java.io.*;

public class Main{
	public static void main(String[] args){
		Scanner stdIn = null;
		List<Integer> list = new ArrayList<Integer>();
		
		try{
			stdIn = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
			while( stdIn.hasNext() ){
				String str = stdIn.next();
				String[] s = str.split(",");
				int number = Integer.parseInt(s[0]);
				double height = Double.parseDouble(s[2]);
				double weight = Double.parseDouble(s[1]);
				if( weight/(height*height) >= 25 ){
					list.add(number);
				}
			}
			if( list.size() == 0 ){
				System.out.println("該当なし");
			} else {
				for(Integer ans : list){
					System.out.println(ans);
				}
			}
		} finally {
			if( stdIn != null ){
				stdIn.close();
			}
		}
	}
}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
using namespace std;
int digit(int,long long);
void ABC060(int,int,int);
void ABC058(string,string);
void line(int);
int main(){
	int n;
	cin>>n;
	if(n==1){
		cout<<1<<endl;
		return 0;
	}
	for(int i=1;i<=n;i++){
		if((i+1)*(i+1)>n){
			cout<<i*i<<endl;
			break;
		}
	}
}
void ABC060(int a,int b,int c){
	
	for(int u=1;u<100;u++){
		if(a*u%b==c){
			cout<<"YES"<<endl;
			break;
			}
		else if(a*u%b==0){
			cout<<"NO"<<endl;
			break;
		}
	}
}
int digit(int n,long long dig){
	return n%(dig*10)/dig;
}
void ABC058(string o,string e){
	int z=o.size(),x=e.size();
	for(int i=0;i<z+x;i++){
		if(i%2==0){
			cout<<o[i/2];
		}
		else{
			cout<<e[(i+1)/2-1];
		}
	}
	cout<<endl;
}
void line(int w){
	for(int k=0;k<w+2;k++){
		cout<<"#";
	}
	cout<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
  
int main() {
    string S;
    cin >> S;
    int N = S.size();
    int sum = 0;

    vector<int> A(N);
    for (int i = 0 ; i < N; i++) {
      A.at(i) = S.at(i) - '0';
    }
    
    for (int i = 0 ; i < N; i++) {
      sum += A.at(i);
    }
    if (sum % 9 == 0){
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}



Measured memory_bytes: 4364
package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scanf("%s", &s)
	r := []rune(s)
	if isPalindrome(r) && isPalindrome(r[:len(r)/2]) && isPalindrome(r[len(r)/2+1:]) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}

}

func isPalindrome(rs []rune) bool {
	for i := 0; i < len(rs)/2; i++ {
		if rs[i] != rs[len(rs)-i-1] {
			return false
		}
	}
	return true
}

func scanIntSlice(size int) []int {
	input := []int{}
	for i := 0; i < size; i++ {
		var in int
		fmt.Scanf("%d", &in)
		input = append(input, in)
	}
	return input
}


Measured memory_bytes: 512
#pragma GCC Optimize("Ofast")
#pragma GCC Optimize "trapv"
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp> 

using namespace std;
//using namespace boost::multiprecision; 

#define FAST ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TC int t; cin >> t; while(t--)
#define li long int
#define ll long long
#define ull unsigned long long 
#define Vec(x) vector <x>
#define Pai(x,y) pair <x,y>
#define Map(x,y) map <x,y>
#define UMap(x,y) unordered_map <x,y>
#define Set(x) set <x>
#define Sta(x) stack <x>
#define Qu(x) queue <x>
#define DQ(x) deque(x)
#define PriorQ(x)	priority_queue <x>
#define bg begin()
#define ed end()
#define sz size()
#define ct(x) count(x)
#define len length()
#define F first
#define S second
#define Makep make_pair
#define ins(x) insert(x)
#define ers(x) erase(x)
#define endl "\n";
#define MOD 1000000007
#define PI 2*acos(0.0)
#define clr() clear()
#define fori0(n) for(int i=0;i<n;i++)
#define foriab(a,b) for(int i=a;i<b;i++)
#define mem0(x) memset(x,0,sizeof(x))
#define mem1(x) memset(x,1,sizeof(x))
#define autoit(x) for(auto it=x.beg;it!=x.ed;it++)
#define count0(x) __builtin_popcount(x)
#define ret return 
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());

const ll Inf=1e9+5;



namespace funset{
bool checkvow(char x){
	return ((0x208222)>>(x&(0x1f)))&1;
	}
ll highpow2(ll x){
	return (x&~(x-1));
	}
bool chk2(ll x){
		return (x&(x-1));
	}	
}

using namespace funset;

ll n, w;
ll wei[101],val[101],dp[1001][10001];

void solve(){
	ll n,x,t;
	cin >> n >> x >> t;
	ll ans=1ll*(n*t)/x;
	if(ans%t){
		cout << ans + (t-ans%t) << endl;
		return;
	}
	cout << ans << endl;
}

int main(){
	auto beg=clock();
	
	FAST
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	//TC
    solve();
	auto ted=clock();
	#ifndef ONLINE_JUDGE
	cout << (double)(ted-beg)/CLOCKS_PER_SEC << endl;
	#endif
	ret 0;
}

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

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
const int MOD = 1000000007;

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


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

const static int NMAX = 50000;
const static int MMAX = 20;
static const int INF = (1 << 29);

int main() {
	int C[MMAX+1];
	int T[MMAX+1][NMAX + 1];
	int n, m;
	cin >> n >> m;
	C[0] = 0;
	for (int i = 1; i <= m; i++) {
		cin >> C[i];
	}
	fill(T[0], T[0] + n + 1, INF);
	for (int i = 0; i < m + 1; i++) {
		T[i][0] = 0;
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (j >= C[i]) {
				T[i][j] = min(T[i - 1][j], T[i][j - C[i]] + 1);
			}
			else {
				T[i][j] = T[i - 1][j];
			}
		}
	}
	cout << T[m][n] << endl;
}

Measured memory_bytes: 7196
#include <cstdio>

int main() {
	int d, n;
	scanf("%d %d", &d, &n);	
	if(d == 0 && n == 100) printf("101\n");
	else if(d == 0) printf("%d\n", n);
	else if(d == 1 && n == 100) printf("10100\n");
	else if(d == 1) printf("%d\n", n*100);
	else if(d == 2 && n == 100) printf("1010000\n");
	else printf("%d\n", n*10000);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;

template<class T> inline void checkmin(T &a,const T &b){if(b<a) a=b;}
template<class T> inline void checkmax(T &a,const T &b){if(b>a) a=b;}

const int inf=1e9+10;
const int maxn=17;

ll dp[1<<maxn],a[maxn][maxn]; 
int n;

int main(){
	cin>>n;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>a[i][j];
	for(int mask=0;mask<(1<<n);mask++){
		vector <int> v;
		for(int i=0;i<n;i++) if(mask&(1<<i)) v.pb(i);
		for(int i=0;i<v.size();i++) for(int j=i+1;j<v.size();j++)
			dp[mask]+=a[v[i]][v[j]];
	}
	for(int msk=0;msk<(1<<n);msk++){
		for(int msk2=msk;msk2;msk2=(msk2-1)&msk){
			checkmax(dp[msk],dp[msk^msk2]+dp[msk2]);
		}
	}
	cout<<dp[(1<<n)-1]<<endl;
	return 0;
}



Measured memory_bytes: 768
w, h, n = map(int, input().split())

xl, xr, yd, yu = 0, w, 0, h
for _ in range(n):
    x, y, a = map(int, input().split())
    if a == 1:
        xl = max(xl, x)
    elif a == 2:
        xr = min(xr, x)
    elif a == 3:
        yd = max(yd, y)
    else:
        yu = min(yu, y)

width = max(xr-xl, 0)
height = max(yu-yd, 0)
print(width*height)


Measured memory_bytes: 3064
#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>

using namespace std;

// dp[i][j] = 価値 j の重み最小値
array<array<uint64_t, 100001>, 101> dp;

constexpr uint64_t INF = 10000000000ull;

int main()
{
    uint64_t n, w;
    cin >> n >> w;

    vector<int64_t> ws(n), vs(n);

    uint64_t max_v = 0;

    for (uint64_t i = 0; i < n; i++)
    {
        cin >> ws[i] >> vs[i];
        max_v += vs[i];
    }

    for (auto& v : dp)
    {
        fill(v.begin(), v.end(), INF);
    }
    dp[0][0] = 0;

    for (uint64_t i = 1; i <= n; i++)
    {
        for (uint64_t v = 0; v <= max_v; v++)
        {
            dp[i][v] = dp[i - 1][v];
        }
        for (uint64_t v = 0; v <= max_v - vs[i - 1]; v++)
        {
            if (dp[i - 1][v] < INF)
            {
                dp[i][v + vs[i - 1]] = min(dp[i][v + vs[i - 1]], dp[i - 1][v] + ws[i - 1]);
            }
        }
    }

    uint64_t ans = 0;
    for (uint64_t i = 0; i <= max_v; i++)
    {
        if (dp[n][i] <= w)
        {
            ans = i;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 79104
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

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

const ll MOD=1e9+7;
const ll INF=1e18;

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

int main(){
    ll a, b, c; cin>>a>>b>>c;
    if(c<=b){
        cout << b+c << endl;
    }
    else{
        ll ans=b*2;
        c-=b;
        if(c<=a){
            cout << ans+c << endl;
        }
        else{
            cout << ans+a+1 << endl;
        }
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define it ::iterator
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double ESP=1e-10;
using namespace std;
int main(){
  int n;
  cin>>n;
  while(n--){
    int an,y,m;
    cin>>an>>y>>m;
    int ma=0;
    rep(i,m){
      int a=an;
      int b,d;
      double c;
      cin>>b>>c>>d;
      if(!b){
	int par=0;
	rep(j,y){
	  par+=(int)(a*c);
	  a-=d;
	}
	a+=par;
      }else{
	rep(j,y){
	  a+=(int)(a*c)-d;
	}
      }
      ma=max(ma,a);
    }
    cout<<ma<<endl;
  }
	

}

Measured memory_bytes: 1232
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5
0 3 2 3 3 1 1 2
1 2 0 2 3 4
2 3 0 3 3 1 4 1
3 4 2 1 0 1 1 4 4 3
4 2 2 1 3 3

output:
0 0
1 2
2 2
3 1
4 3
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2
D_MAX = int(1e7 + 1)


def generate_adj_matrix(v_info):
    for each in v_info:
        v_index, v_adj_length, *v_adj_list = map(int, each)
        # assert len(v_adj_list) == v_adj_length * 2
        for pair in zip(v_adj_list[::2], v_adj_list[1::2]):
            init_adj_matrix[v_index][pair[0]] = pair[1]

    return init_adj_matrix


def dijkstra_path():
    # path search init
    path_list[init_vertex_index] = 0
    path_heap = []
    # heapq: rank by tuple[0], here ranked by d[u]
    hp.heappush(path_heap, (0, init_vertex_index))
    while len(path_heap) >= 1:
        current_vertex_index = hp.heappop(path_heap)[1]

        color[current_vertex_index] = BLACK

        for adj_vertex_index in range(vertices_num):
            current_adj_weight = adj_table[current_vertex_index].get(adj_vertex_index, -1)
            if current_adj_weight < 0:
                continue
            elif color[adj_vertex_index] is not BLACK:
                # alt: d[u] + w[u,v]
                alt_path = path_list[current_vertex_index] + current_adj_weight
                if alt_path < path_list[adj_vertex_index]:
                    # update path_list
                    path_list[adj_vertex_index] = alt_path
                    # update heap
                    hp.heappush(path_heap, (alt_path, adj_vertex_index))
                    parent_list[adj_vertex_index] = current_vertex_index
                    color[adj_vertex_index] = GRAY

    return path_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    init_vertices_table = map(lambda x: x.split(), _input[1:])
    # assert len(init_vertices_table) == vertices_num

    parent_list, path_list = [-1] * vertices_num, [D_MAX] * vertices_num
    color = [WHITE] * vertices_num
    init_adj_matrix = tuple(dict() for _ in range(vertices_num))
    init_vertex_index = 0

    adj_table = generate_adj_matrix(init_vertices_table)
    ans = dijkstra_path()
    for i, v in enumerate(ans):
        print(i, v)

Measured memory_bytes: 8252
#include<iostream>
    #include<stdio.h>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<float.h>
    #include<iomanip>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<math.h>
    #include<sstream>
    #include<set>
    #include<map>
    #include<queue>
    #include<deque>

    #define INF 1e9
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
    #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
    #define vec(type,n) vector<type>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))

    using namespace std;
    using ll = long long;
	  
    int main(){
      int n;
      cin>>n;
      VEC(ll,a,n);
      deque<ll> dq;
      rep(i,n){
        if(i%2 == 0)dq.push_front(a[i]);
        else dq.push_back(a[i]);
      }
      if(n%2 == 1)for(auto d : dq)cout<<d<<" ";
      else {
        reverse(dq.begin(),dq.end());
        for(auto d : dq)cout<<d<<" ";
      }
    }

Measured memory_bytes: 5376
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e3+7;
int f[N][N];
char s[N], t[N];
vector<char> vec;
pair<int, int> g[N][N];
int main()
{
	int n, m;
	scanf("%s%s", s+1, t+1);
	n = strlen(s+1);
	m = strlen(t+1);
	for(int i = 0; i <= n; i++)
	{
		for(int j = 0; j <= m; j++)
		{
			g[i][j] = make_pair(0, 0);
		}
	}
	for(int i = 1; s[i] != '\0'; i++)
	{
		for(int j = 1; t[j] != '\0'; j++)
		{
			if(f[i][j-1]>f[i][j])
			{
				f[i][j] = f[i][j-1];
				g[i][j] = make_pair(i, j-1);
			}
			if(f[i-1][j]>f[i][j])
			{
				f[i][j] = f[i-1][j];
				g[i][j] = make_pair(i-1, j);
			}
			if(s[i]==t[j]&&f[i-1][j-1]+1>f[i][j])
			{
				f[i][j] = f[i-1][j-1]+1;
				g[i][j] = make_pair(i-1, j-1);
			}
		}
	}
	int x = n, y = m;
	while(x&&y)
	{
		int fx, fy;
		fx = g[x][y].first;
		fy = g[x][y].second;
		if(f[x][y]-f[fx][fy]==1)
		{
            vec.push_back(s[x]);
        }
        x = fx;
        y = fy;
	}
	while(vec.size())
	{
		printf("%c", vec.back());
		vec.pop_back();
	}
	puts("");
	return 0;
}

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

using namespace std;

#define ld long double
#define N 3000
int n; ld p[N], f[N][N];

int main()
{
    cin >> n;
    for (int i=1; i<=n; i++)
        cin >> p[i];
    f[0][0] = 1;
    for (int i=1; i<=n; i++)
    {
        f[i][0] = f[i-1][0] * (1 - p[i]);
        for (int j=1; j<=i ;j++)
        {
            f[i][j] = f[i-1][j-1] * p[i] + f[i-1][j] * (1 - p[i]);
        }
    }
    ld r = 0;
    for (int i=n; i>n/2; i--)
    {
        r += f[n][i];
    }
    cout << setprecision(10) << fixed << r;
    return 0;
}


Measured memory_bytes: 139136
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000007;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N;
	cin >> N;

	vector<Int> a(N);
	for (Int i = 0; i < N; i++) {
		cin >> a[i];
	}

	vector<Int> sum(N + 1);//xiに到達するまでにかかる総コスト
	sum[0] = abs(a[0]);

	for (Int i = 1; i < N; i++) {
		sum[i] = sum[i - 1] + abs(a[i] - a[i - 1]);
	}
	sum[N] = sum[N - 1] + abs(a[N - 1]);


	Int temp = 0;
	for (Int i = 0; i < N; i++) {
		if (i == 0) {
			temp = sum[N] - sum[1] + abs(a[1]);
			printf("%lld\n", temp);
		}
		else if (i == N - 1) {
			temp = sum[N - 2] + abs(a[N - 2]);
			printf("%lld\n", temp);
		}
		else {
			temp = sum[i - 1] + sum[N] - sum[i + 1] + abs(a[i - 1] - a[i + 1]);
				printf("%lld\n", temp);
		}
	}

}

Measured memory_bytes: 2816
using System;
class Program
{
	static void Main(string[] args)
	{
		// 整数の入力
		string S = Console.ReadLine();
		// スペース区切りの整数の入力
		string[] Weathers = {"Sunny","Cloudy","Rainy"};
		int num = 0;
      	for(int i = 0 ;i<Weathers.Length;i++){
        	if ( S== Weathers[i]){
            	num = i;
            }
        }
      	num++;
      	if ( num == Weathers.Length){
        	num = 0;
        }
		//出力
		Console.WriteLine(Weathers[num]);
	}
}


Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
int main()
{
  ll s;
	cin>>s;
	vector<ll> dp(s+1,0);
	dp[0]=1;
	for(int i=3;i<=s;++i){
		for(int j=i-3;j>=0;--j)
			(dp[i]+=dp[j])%=mod;
	}
	cout<<dp[s];
}


Measured memory_bytes: 3600
#include <iostream>


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

    for (int i = 1; i <= n; i++) {
        if (i % 3 == 0) {
            std::cout << " " << i;
            continue;
        } else if (i % 10 == 3) {
            std::cout << " " << i;
            continue;
        }

        int a = i / 10;
        if (a % 10 == 3) {
            std::cout << " " << i;
            continue;
        }

        int b = a / 10;
        if (b % 10 == 3) {
            std::cout << " " << i;
            continue;
        }

        int c = b / 10;
        if (c % 10 == 3) {
            std::cout << " " << i;
            continue;

        }



    }

    std::cout << std::endl;

    return 0;
}

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

#define what_is(x)    cerr<<#x<<" is "<<x<<"\n";
#define rep(i,a,n)    for(int i=a; i<=n; ++i)
#define rep1(i,a,n)   for(int i=a; i>=n; --i)
#define pb            push_back
#define mp            make_pair
#define int           long long
#define fr            first
#define sc            second
#define vc            vector
#define sz(v)         (int)v.size()
#define all(x)        (x).begin(),(x).end()
#define rall(x)       (x).rbegin(),(x).rend()
#define M             1000000007
#define MM            998244353
#define PI            3.14159265358979
#define INF           1000000000000000

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mii;

int n,m,ans; string str;

int solve(){
    cin>>n;
    int a[n]; rep(i,0,n-1) cin>>a[i];
    int x=1;
    rep(i,0,n-1){
        if(a[i]==x){
            x++;
        }
    }
    if(x==1) cout<<-1;
    else cout<<n-x+1;
    return 0;
}

signed main() {
    ios::sync_with_stdio(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>
template<typename TYPE>
inline void read(TYPE&x){
	x=0;int w=1;register char c=getchar();for(;c<'0'||c>'9';c=getchar()) if (c=='-') w=-1;
	for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=getchar());x*=w;
}
int n,m;
int main(){
	read(n);read(m);
	return printf("%d\n",(n-1)*(m-1)),0;
}

Measured memory_bytes: 128
// Problem : D - Snuke Numbers
// Contest : AtCoder Regular Contest 099
// URL : https://atcoder.jp/contests/arc099/tasks/arc099_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include "bits/stdc++.h"
using ll = long long;
using namespace std;
#define size(x) (int)x.size()

const int N = 1e6 + 1;

ll binpow(ll n, ll k) {
	ll ans = 1;
	while (k) {
		if (k & 1) {
			ans = ans * n;
		}
		n = n * n;
		k >>= 1;
	}
	return ans;
}

int main() { cin.tie(0)->sync_with_stdio(0);
	vector<ll> ans;
	for (int i = 0; i <= 9; i++) {
		ans.push_back(i);
	}
	for (int i = 19; i < 100; i += 10) {
		ans.push_back(i);
	}
	for (ll i = 2; i <= 10; i++) {
		for (ll j = i * binpow(10, i) - 1; j < i * binpow(10, i + 1); j += binpow(10, i)) {
			ans.push_back(j);
		}
	}
	for (ll i = 11; i <= 15; i++) {
		for (ll j = 11 * binpow(10, i) - 1; j < binpow(10, i + 2); j += binpow(10, i)) {
			ans.push_back(j);
		}
	}
	for (ll i = binpow(10, 14) + binpow(10, 12) - 1; i < binpow(10, 14) + binpow(10, 13); i += 1e12) {
		ans.push_back(i);
	}
	ans.pop_back();
	sort(ans.begin(), ans.end());
	int k;
	cin >> k;
	for (int i = 1; i <= k; i++) {
		cout << ans[i] << '\n';
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int mp[1001][1001];

int main(){
	int W;char c;
	for(int num = 0;cin >> W&&W;num++){
		int v[1000], w[1000], n;
		cin >> n;
		fill((int*)mp, (int*)(mp+n+1), 0);
		
		for(int i = 0;i < n;i++){
			cin >> v[i] >> c >> w[i];
			for(int j = 0;j < W+1;j++){
				if(j < w[i])mp[i+1][j] = mp[i][j];
				else mp[i+1][j] = max(mp[i][j], mp[i][j-w[i]]+v[i]);
			}
		}
		
		int ans = 0;
		for(int i = 1;i < W+1;i++){
			if(mp[n][i] > mp[n][ans])ans = i;
		}
		cout << "Case " << num+1 << ":" << endl;
		cout << mp[n][ans] << endl << ans << endl;
	}
	return 0;
}
/*
1
y eazqyp pnop pngtg ye obmpngt xmybp mr lygw
*/

Measured memory_bytes: 6912
using System;

namespace abc139_a
{
    class Program
    {
        static void Main(string[] args)
        {
            char[] s = Console.ReadLine().ToCharArray();

            char[] t = Console.ReadLine().ToCharArray();

            int result = 0;
            for (int index = 0; index < 3; index++)
            {
                


                if (s[index].ToString()== t[index].ToString())
                {
                    result++;
                }

            }

            

            Console.WriteLine(result);
        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n) for(int (i)=((n)-1);(i)>=0;(i)--)
#define itn int
#define all(x) (x).begin(),(x).end()
const long long INF = 1LL << 60;
const int MOD = 1000000007;
signed main(void){
    int n,z,w; cin>>n>>z>>w;
    vector <int> a(n); 
    rep(i,n) cin>>a[i];
    if(n==1) {cout<<abs(a[0]-w)<<endl; return 0;}
    else cout<<max(abs(a[n-1]-w), abs(a[n-2]-a[n-1]))<<endl;
}


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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  ll X,Y;
  cin>>X>>Y;
  ll n=X;
  ll ans=0;
  while(n<=Y){
    ans++;
    n*=2;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <algorithm>
#include <functional>

#include <vector>
#include <tuple>
#include <map>

using namespace std;

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

	string s;
	cin >> s;

	if (s == "ABC")
	{
		cout << "ARC";
	}
	else
	{
		cout << "ABC";
	}

	return 0;
}

Measured memory_bytes: 3640
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int N=200005;
struct node
{
    int u,v,nxt;
}edge[2*N];
struct Tree
{
    int l,r,w,siz,f;
}T[2*N];
int n,m,cnt=0,num=1,root=1,a[N],b[N],head[N];
int deep[N],fa[N],son[N],tot[N],top[N],idx[N];
void AddEdge(int x,int y)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].nxt=head[x];
    head[x]=num++;
}
int dfs1(int now,int f,int dep)
{
    deep[now]=dep;
    fa[now]=f;
    tot[now]=1;
    int maxson=-1;
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(edge[i].v==f) continue;
        tot[now]+=dfs1(edge[i].v,now,dep+1);
        if(tot[edge[i].v]>maxson) maxson=tot[edge[i].v],son[now]=edge[i].v;
    }
    return tot[now];
}
void update(int k)
{
    T[k].w=T[ls].w+T[rs].w;
}
void Build(int k,int ll,int rr)
{
    T[k].l=ll;T[k].r=rr;T[k].siz=rr-ll+1;
    if(ll==rr)
    {
        T[k].w=a[ll];
        return;
    }
    int mid=(ll+rr)>>1;
    Build(ls,ll,mid);
    Build(rs,mid+1,rr);
    update(k);
}
void dfs2(int now,int topf)
{
    idx[now]=++cnt;
    a[cnt]=b[now];
    top[now]=topf;
    if(!son[now]) return;
    dfs2(son[now],topf);
    for(int i=head[now];i!=-1;i=edge[i].nxt)
      if(!idx[edge[i].v]) dfs2(edge[i].v,edge[i].v);
}
void pushdown(int k)
{
    if(!T[k].f) return ;
    T[ls].w=T[ls].w+T[ls].siz*T[k].f;
    T[rs].w=T[rs].w+T[rs].siz*T[k].f;
    T[ls].f=T[ls].f+T[k].f;
    T[rs].f=T[rs].f+T[k].f;
    T[k].f=0;
}
void IntervalAdd(int k,int ll,int rr,int val)
{
    if(ll<=T[k].l&&T[k].r<=rr)
    {
        T[k].w+=T[k].siz*val;
        T[k].f+=val;
        return;
    }
    pushdown(k);
    int mid=(T[k].l+T[k].r)>>1;
    if(ll<=mid) IntervalAdd(ls,ll,rr,val);
    if(rr>mid) IntervalAdd(rs,ll,rr,val);
    update(k);
}
int IntervalSum(int k,int ll,int rr)
{
    int ans=0;
    if(ll<=T[k].l&&T[k].r<=rr)
        return T[k].w;
    pushdown(k);
    int mid=(T[k].l+T[k].r)>>1;
    if(ll<=mid) ans=ans+IntervalSum(ls,ll,rr);
    if(rr>mid)  ans=ans+IntervalSum(rs,ll,rr);
    return ans;
}
void TreeSum(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        ans=ans+IntervalSum(1,idx[top[x]],idx[x]);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]) swap(x,y);
    ans=ans+IntervalSum(1,idx[x],idx[y]);
    cout<<ans<<" ";
}
int main()
{
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n-1;i++)
    {
    	int x,y;
    	cin>>x>>y;
        AddEdge(x,y);
		AddEdge(y,x);
    }
    dfs1(root,0,1);
    dfs2(root,root);
    Build(1,1,n);
    while(m--)
    {
    	int x,y;
    	cin>>x>>y;
        IntervalAdd(1,idx[x],idx[x]+tot[x]-1,y);
    }
    for(int i=1;i<=n;i++) TreeSum(i,i);
    cout<<endl;
    return 0;
}


Measured memory_bytes: 37504
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define mp make_pair
#define fi first
#define sc second
int n;
int x[300000];
int y[300000];
int main(){
	cin >> n;

	REP(i,n) {
		cin >> x[i];
		y[i] = x[i];
	}

	sort(y,y + n);

	int a = y[n / 2 - 1];
	int b = y[n / 2];

	/*if(a == b) {
		REP(i,n) {
			cout << a << endl;
		}
		return 0;
	}*/

	REP(i,n) {
		if(x[i] <= a) {
			cout << b << endl;
		}else {
			cout << a << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 3712