akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
#include <map>
#include <stack>
using namespace std;
typedef long long int lli;
#define urept(soeji, start, n) for (int soeji = start; soeji < n; soeji++)
#define drept(soeji, start, n) for (int soeji = start; soeji > n; soeji--)
int main(void)
{
    int N;
    cin >> N;
    lli sum = 0;
    for (int i = 1; i <= N; i++)
    {
        if (i % 3 != 0 && i % 5 != 0)
        {
            sum += i;
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef double db;
typedef vector<ll> VI;
typedef vector<pair<ll,ll> > VII;
typedef map<ll,ll> mll;
typedef pair<ll,ll> pll;
//
#define M 1000000007
#define INF (ll)0x3f3f3f3f3f3f3f3f
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define itr iterator
#define GO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void fileioe(){
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout); 
	freopen("error.txt","w",stderr);
}

void error_out() { cerr << endl; }
template <typename Head, typename... Tail>
void error_out(Head H, Tail... T) {
  cerr << " " << H;
  error_out(T...);
}
void time_elapsed(){
  cerr<<"\nTime Elapsed : " << 1.0*clock() / CLOCKS_PER_SEC << " s\n";
}
#ifndef ONLINE_JUDGE
#define error(...) cerr << "[" << #__VA_ARGS__ << "]:", error_out(__VA_ARGS__)
#define fioe() fileioe()
#define time() time_elapsed()
#else
#define error(...) 1
#define fioe() 1
#define time() 1
#endif

ll power(ll a,ll b){
	if(a==0)return 0;
	if(b==0)return 1;
	ll small=power(a,b/2);
	if(b%2==0){
		return small*small;
	}
	return small*small*a;
}
//
int main()
{
	GO
	//fioe();
	ll a,b;
	cin>>a>>b;
	ll aa=0,bb=0;
	for(ll i=0;i<a;i++){
		bb=bb+power(10,i)*b;
	}
	for(ll i=0;i<b;i++){
		aa=aa+power(10,i)*a;
	}
	if(aa>bb){
		cout<<aa<<endl;
	}
	else{
		cout<<bb<<endl;
	}
	time();
	return 0;
}

Measured memory_bytes: 256
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

Q = I()
lr = [LI() for i in range(Q)]

import math

def sieve_of_eratosthenes(n):
    prime_list = []  # n以下の素数のリスト
    A = [1]*(n+1)    # A[i] = iが素数なら1,その他は0
    A[0] = A[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if A[i]:
            prime_list.append(i)
            for j in range(i**2,n+1,i):
                A[j] = 0
    for i in range(math.floor(math.sqrt(n)),n+1):
        if A[i] == 1:
            prime_list.append(i)
    return A

prime = sieve_of_eratosthenes(10**5)
prime_like_2017 = [0]*(10**5+1)
prime_like_2017[3] = 1

for i in range(3,10**5+1):
    if prime[i] == 0:
        continue
    elif i == 2:
        continue
    elif i == 3:
        prime_like_2017[i] = 1
    elif i % 4 == 3:
        continue
    else:
        if prime[(i+1)//2] == 1:
            prime_like_2017[i] = 1

from itertools import accumulate

P = list(accumulate(prime_like_2017))  # P[i] = iまでに2017に似た数が何個あるか

for i in range(Q):
    print(P[lr[i][1]]-P[lr[i][0]-1])

Measured memory_bytes: 65628
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[11];
bool fd(int n){
	while(n>0){
		int m=n%10;
		for(int i=1;i<=k;i++){
			if(a[i]==m) return false;
		}
		n/=10;
	}
	return true;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		cin>>a[i];
	} 
	for(int i=n;;i++){
		if(fd(i)){
			cout<<i<<endl;
			return 0;
		}
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
using namespace std;

#include<map>
#include<set>
#include<queue>

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = 1000000;

int N;
int a[100000];

int main() {
    cin >> N;
    rep(i, N){ cin >> a[i]; }
    sort(&a[0], &a[N]);

	cout << (a[N-1] - a[0]) << endl;
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define REP(NAME, NUM) for (int NAME = 0; NAME < (NUM); ++NAME)
#define BREP(NAME, NUM) for (int NAME = (NUM)-1; NAME >= 0; --NAME)
#define ALL(NAME) (NAME).begin(), (NAME).end()

#define cMOD 1000000007ULL
#define cINF ((1ull<<62)-1)
#define cINFINT ((1<<30)-1)

int main()
{
    ll n,m; cin>>n>>m;
    vector<ll> a( m, 0 );
    REP( i, a.size() ) cin >> a[i];
   
    vector<ll> dp(n+1,0);
    dp[0] = 1;
    
    ll ai = 0;
    REP(i,n+1) if(i!=0)
    {
        if( ai < a.size() )
        {
            while( a[ai] < i ) ++ai;
            if( a[ai] == i ) continue;
        }
        dp[i] = dp[i-1];
        if(i!=1) dp[i] = ( dp[i] + dp[i-2] ) % cMOD;
    }

    cout << dp[n] << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

using namespace std;

// Lucas Number
int main(){
    int input;
    uint64_t lucas=0;
    uint64_t lucas_sub2=2, lucas_sub1=1;

    cin >> input;

    if(input==1){
        lucas = lucas_sub1;
    }
    else if(input >= 2 && input <= 86){
        input--;
        while(input--){
            lucas = lucas_sub1 + lucas_sub2;
            lucas_sub2 = lucas_sub1;
            lucas_sub1 = lucas;
        }
    }
    else{
        return 0;
    }

    // uint64_t hi = (uint64_t)(lucas >> 64);
    // uint64_t lo = (uint64_t)(lucas & 0x0000000000000000FFFFFFFFFFFFFFFF);

    cout << lucas << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
 
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef pair<int, int> pi;


int n;

void dfs(string s, int mx){
  if (s.size() == n){
    cout << s << endl;
    return;
  }
  rep(i, mx+1){
    char c_next = 'a' + i;
    dfs(s + c_next, max(mx, i+1));
  }
  return;
}

int main() {
  cin >> n;
  dfs("", 0);
  return 0;
}

Measured memory_bytes: 1536
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){
  int M=0;
  int a[100];
  int n;
  int i,j;
  scanf("%d",&n);
  int m = (n%7)%4;
  if(n%7==0){
    printf("Yes");
  }else{
    while(1){
      if(m%4==0){
        printf("Yes");
        break;
      }else{
        m=m+7;
        if(m>n){
          printf("No");
          break;
        }
      }
      }
    }
}

Measured memory_bytes: 128
#include <iostream>
/*
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <functional>
#include <stack>
#include <queue>
#include <string>
#include <unordered_map>
*/
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

//const ll nmax=100001;
//const ll inf=1000000000+7;
const ll nmax=500;
const ll mmax=200000;
const ll qmax=100000;
ll x[nmax+1][nmax+1],c[nmax+1][nmax+1];


int main(){

    ll N,M,Q;
    ll l,r;

    cin>>N>>M>>Q;

    for(ll i=0;i<M;i++){
        cin>>l>>r;
        x[l][r]++;
    }
    ll t=0;
    for(ll i=1;i<=N;i++){
        for(ll j=1;j<=N;j++){
            t=0;
            for(ll k=1;k<=j;k++){
                t+=x[i][k];
            //c[i][j]+=x[i][k];
            }
            c[i][j]=t;
        }
    }

    ll p,q;
    ll ans=0;
    for(ll i=0;i<Q;i++){
        cin>>p>>q;
        ans=0;
        for(ll j=p;j<=q;j++){
            ans+=(c[j][q]-c[j][j-1]);
        }
        cout<<ans<<endl;
    }

    return 0;
}



Measured memory_bytes: 4864
#include<iostream>
#include <iomanip>
#include <ios>
#include <vector>
#include <string>
#include <algorithm>
#include <string>
#include<limits>
#include<cstdlib>
#include<functional>
#include<cassert>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#define fi(p) for(int i=0;i<(p);i++)
#define ce(d) cout<<d<<endl;
#define ll long long
#define sorts(c) sort((c).begin(),(c).end());

using namespace std;

void solve() {
	string s;
	cin >> s;
	bool flag = false;

	fi(s.size()) {
		if (i%2==1) {
			if (s[i] == 'L' || s[i] == 'U' || s[i] == 'D') {
				
			}
			else {
				break;
			}
		}
		else
		{
			if (s[i] == 'R' || s[i] == 'U' || s[i] == 'D') {
				
			}
			else {
				break;
			}
		} 

		if (i == s.size()-1) {
			flag = true;
		}
	}

	if (flag == true) {
		ce("Yes");
	}
	else {
		ce("No");
	}
}



int main()
{

	solve();

	int a;//止める用
	cin >> a;
	return 0;
}

Measured memory_bytes: 256
// Brijesh Panara (201601074)
// DAIICT (India)
#include <bits/stdc++.h>
#include <time.h>
using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define FILL(a,b) memset((a),(b),sizeof((a)))
#define precision(x,d) cout<<fixed<<setprecision(d)<<x
#define minQueue priority_queue<ll,vector<ll>,greater<ll> > 
#define maxQueue priority_queue<ll,vector<ll>,less<ll> > 

#define deb1(x) cout<<#x<<" : "<<x<<endl;
#define deb2(x,y) cout<<#x<<" : "<<x<<" "<<#y<<" : "<<y<<endl;
#define deb3(x,y,z) cout<<#x<<" : "<<x<<"   "<<#y<<" : "<<y<<"  "<<#z<<" : "<<z<<endl;

#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define READ freopen("input.txt","r",stdin);
#define WRITE freopen("output.txt","w",stdout);
#define RANDOM srand(time(NULL));

#define MOD 1000000007
#define NAX 1000005
#define INF LONG_LONG_MAX
#define MINF LONG_LONG_MIN



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

    if(a==b && b==c)
    	cout<<"Yes"<<endl;
    else
    	cout<<"No"<<endl;
    
    return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>){
    val inputs = readLine()?.split(" ")?.map {it.toInt()} ?: return 
    when {
        inputs[0] > inputs[1] -> println("a > b") 
        inputs[0] < inputs[1] -> println("a < b")
        else ->  println("a == b")
    }
}


Measured memory_bytes: 31992
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<vector<int>> h(n + 1, vector<int>(3));
  for(int i = 1; i < n + 1; ++i){
    cin >> h[i][0] >> h[i][1] >> h[i][2];
  }
  int dp[n + 1][3];
  for(int i = 0; i < 3; ++i) dp[0][i] = 0;
  for(int i = 1; i < n + 1; ++i){
    dp[i][0] = max(dp[i - 1][1] + h[i][0], dp[i - 1][2] + h[i][0]);
    dp[i][1] = max(dp[i - 1][0] + h[i][1], dp[i - 1][2] + h[i][1]);
    dp[i][2] = max(dp[i - 1][0] + h[i][2], dp[i - 1][1] + h[i][2]);
  }
  cout << (max(dp[n][0], max(dp[n][1], dp[n][2]))) << endl;
}

Measured memory_bytes: 6912
N,K=map(int,input().split())

a=N//K


if a>=1:
    s=N-K*a
    if s>=abs(s-K):
        print(int(abs(s-K)))
    else:
        print(int(s))

elif a==0 and N>=(abs(N-K)):
    print(int(abs(N-K)))

else:
    print(int(N))

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

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

const long long INF = 1LL<<60;

//input
string s,t;

//dp table 
int dp[3100][3100] = {0}; //IV, IC 0

int main(){
    cin >> s >> t;
    
    //dp loop
    for (int i = 0; i < s.size(); i++){
        for (int j = 0; j < t.size(); j++){
            if (s[i] == t[j]) chmax(dp[i+1][j+1], dp[i][j] + 1);
            chmax(dp[i+1][j+1], dp[i+1][j]);
            chmax(dp[i+1][j+1], dp[i][j+1]);
        }
    }
    
    
    //復元する
    string res = "";
    int i = s.size(), j = t.size();
    
    while (i > 0 && j > 0){
        
        // (i,j-1) -> (i, j)
        if (dp[i][j] == dp[i-1][j]) i--;
        else if (dp[i][j-1] == dp[i][j]) j--;
        else{
            res = s[i-1] + res;
            i--, j--;
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 37120
#include <stdio.h>
int main(void){
	
int num;


scanf("%d",&num);

if((100<=num)&&(num<=111))
printf("111");
if((112<=num)&&(num<=222))
printf("222");
if((223<=num)&&(num<=333))
printf("333");
if((334<=num)&&(num<=444))
printf("444");
if((445<=num)&&(num<=555))
printf("555");
if((556<=num)&&(num<=666))
printf("666");
if((667<=num)&&(num<=777))
printf("777");
if((778<=num)&&(num<=888))
printf("888");
if((889<=num)&&(num<=999))
printf("999");



return 0;
}

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


vector<ll> inv,fact,invfact;
void mod_build(int n=101010){
    fact.resize(n+1);
    inv.resize(n+1);
    invfact.resize(n+1);
    fact[0]=inv[0]=invfact[0]=1;
    inv[1]=1;
    rep(i,n){
        fact[i+1]=fact[i]*(i+1)%mod;
        if(i>0)inv[i+1]=mod-inv[mod%(i+1)]*(mod/(i+1))%mod;
        invfact[i+1]=invfact[i]*inv[i+1]%mod;
    }
}
ll perm(int n,int k){
    if(n<0||k<0||k>n)return 0;
    return fact[n]*invfact[n-k]%mod;
}
ll comb(int n,int k){
    if(n<0||k<0||k>n)return 0;
    return (fact[n]*invfact[n-k]%mod)*invfact[k]%mod;
}
ll powmod(ll n,ll k){
    k%=mod-1;
    if(k<0)k+=mod-1;
    ll ret=1;
    while(k){
        if(k&1)ret=ret*n%mod;
        n=n*n%mod;
        k>>=1;
    }
    return ret;
}
int main(){
    int n,k;
    cin>>n>>k;
    mod_build();
    if(n==k){
        cout<<1<<endl;
        rep(i,n-1)cout<<0<<endl;
        return 0;
    }
    rep(i,k){
        ll ans = 0;
        ans += comb(k-1,i)*comb(n-k-1,i-1)%mod;
        ans += 2*comb(k-1,i)*comb(n-k-1,i)%mod;
        ans += comb(k-1,i)*comb(n-k-1,i+1)%mod;
        cout<<ans%mod<<endl;
    }
    return 0;
}

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

namespace C
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nk = RArInt();
            int n = nk[0];
            int k = nk[1];

            double[] ps = new double[nk[0]];

            for (int i = 0; i < ps.Length; i++)
            {
                if (i + 1 >= k)
                {
                    ps[i] = 1;
                }
                else
                {
                    double r = 0;
                    while ((i + 1) * Math.Pow(2, r) < k)
                    {
                        r++;
                    }
                    double j = Math.Pow(2, r);
                    ps[i] = 1 / j;
                }
            }

            Console.WriteLine(ps.Sum() / n);

        }
        static string RSt() { return Console.ReadLine(); }
        static int RInt() { return int.Parse(Console.ReadLine().Trim()); }
        static long RLong() { return long.Parse(Console.ReadLine().Trim()); }
        static double RDouble() { return double.Parse(Console.ReadLine()); }
        static string[] RArSt(char sep = ' ') { return Console.ReadLine().Trim().Split(sep); }
        static int[] RArInt(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => int.Parse(e)); }
        static long[] RArLong(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => long.Parse(e)); }
        static double[] RArDouble(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => double.Parse(e)); }
        static string WAr<T>(IEnumerable<T> array, string sep = " ") { return string.Join(sep, array.Select(x => x.ToString()).ToArray()); }
    }
}


Measured memory_bytes: 13268
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.IllegalArgumentException
import java.lang.StringBuilder
import java.lang.reflect.Modifier
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    var n = sc.nextInt()
    val lst = mutableListOf<Int>()
    while (n != 0) {
        if (n % 2 == 0) {
            lst.add(0)
        } else {
            lst.add(1)
            n--
        }
        n /= -2
    }
    if (lst.count() == 0) {
        lst.add(0)
    }
    println(lst.reversed().joinToString(""))
}

fun main() {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}

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

int main() {
  char c;
  cin >> c;
  
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
    cout << "vowel" << endl;
  
  else
    cout << "consonant" << endl;
  
}


Measured memory_bytes: 256
/* ITP1_8_C */
#include <stdio.h>
#include <stdlib.h>

#define INPUT_MAX 1201
#define RESULT_ARRAY_SIZE 26
#define CHAR_CODE_LARGE_A 65
#define CHAR_CODE_LARGE_Z 90
#define CHAR_CODE_SMALL_A 97
#define CHAR_CODE_SMALL_Z 122

/* ?????????????????¢??° */
void do_count(char *target, short *result);

int main(void)
{
	short ii, idx = 0;
	char input_char = '\0';
	char input[INPUT_MAX];
	for( ii = 0; ii < INPUT_MAX; ii++ )
	{
		input[ii] = '\0';
	}
	
	// ??\????????????
	ii = 0;
	while( EOF != scanf("%c", &input_char) )
	{
		input[ii] = input_char;
		ii++;
	}

	// ??????
	short result[RESULT_ARRAY_SIZE];
	for( ii = 0; ii < RESULT_ARRAY_SIZE; ii++ )
	{
		result[ii] = 0;
	}
	do_count(input, result);
	
	// ???????????????
	for( ii = 0; ii < RESULT_ARRAY_SIZE; ii++ )
	{
		printf("%c : %d\n", CHAR_CODE_SMALL_A + ii, result[ii]);
	}
	
	return 0;
}

/* ?????????????????¢??° */
void do_count(char *target, short *result)
{
	short ii = 0;
	// ??\?????????????????§?????????
	while( '\0' != target[ii] )
	{
		if( CHAR_CODE_LARGE_A <= target[ii] && CHAR_CODE_LARGE_Z >= target[ii] )
		{
			result[target[ii] - CHAR_CODE_LARGE_A]++;
		}
		else if( CHAR_CODE_SMALL_A <= target[ii] && CHAR_CODE_SMALL_Z >= target[ii] )
		{
			result[target[ii] - CHAR_CODE_SMALL_A]++;
		}
		ii++;
	}
}

Measured memory_bytes: 544
n=int(input())
if n==1:
  print('Yes')
  print('2\n1 1\n1 1')
  exit()
for i in range(n):
  if i*(i+1)//2==n:break
else:
  print('No')
  exit()
m=i
a=[[0]*m for _ in range(m)]
i=0
while n>0:
  for j in range(i+1):
    a[i][j]=n
    n-=1
  i+=1
a=a[::-1]
s=[[] for _ in range(m+1)]
for i in range(m):
  s[i]=a[i][:m-i]
  for j in range(i):
    s[i]+=[a[i-1-j][m-i-1]]
for i in range(m):
  s[-1]+=[a[i][m-i-1]]
print('Yes')
print(len(s))
for i in s:
  print(len(i),*i)

Measured memory_bytes: 77752
import java.util.*;
class Main {
	public static void main (String[] args) throws java.lang.Exception {
		Scanner sc = new Scanner(System.in);
		int a, c = 0;
		while(true) {
			a = sc.nextInt();
			if(a == 0) break;
			System.out.println("Case " + (++c) + ": " + a);
		}
	}
}



Measured memory_bytes: 44924
INF = 99999999999

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

dp = [INF for _ in range(N)]

dp[0] = 0
dp[1] = abs(hN[1] - hN[0])

for i in range(2, N):
    diff1 = dp[i - 1] + abs(hN[i - 1] - hN[i])
    diff2 = dp[i - 2] + abs(hN[i - 2] - hN[i])
    dp[i] = min(diff1, diff2, dp[i])

    # print("i={}, dp={}".format(i, dp))

print(dp[N - 1])


Measured memory_bytes: 13976
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

template <class T>
struct Unionfindw {
  // tree number
  vector<int> par;
  // tree rank
  vector<int> treerank;
  // edge weight
  vector<T> weight;
  // constructor
  Unionfindw(int n = 1, T initialnum = 0) {
    stree(n + 1, initialnum);
  }
  // make and initialization
  void stree(int n = 1, T initialnum = 0) {
    par.assign(n, -1);
    treerank.assign(n, 0);
    weight.assign(n, initialnum);
  }
  // search root
  int root(int x) {
    if(par[x] < 0) return x;
    int rx = root(par[x]);
    weight[x] += weight[par[x]];
    return par[x] = rx;
  }
  // is same?
  bool issame(int x, int y) { return root(x) == root(y); }
  // calculate weight
  T calcw(int x) {
    root(x);
    return weight[x];
  }
  // add
  // x+w = y
  // already added, return 0
  bool uni(int x, int y, T w = 0) {
    w += calcw(x);
    w -= calcw(y);
    x = root(x);
    y = root(y);
    if(x == y) return 0;
    if(treerank[x] > treerank[y]) swap(x, y);
    if(treerank[x] == treerank[y]) ++treerank[x];
    par[y] -= size(x);
    par[x] = y;
    weight[x] = -w;
    return 1;
  }

  int size(int x) { return -par[root(x)]; }

  // calculate difference between x and y (y-x)
  // if not same tree, return 1
  T calcdiff(int x, int y) {
    if(!issame(x, y)) return -1;
    return calcw(y) - calcw(x);
  }
};

long long n, m;
long long cnt[100005] = {0};
vector<pair<int, int>> v;
Unionfindw<long long> uf;
vector<long long> ans;

void solve();

int main() {
  cin >> n >> m;
  for(int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    v.push_back(make_pair(a, b));
  }
  reverse(v.begin(), v.end());
  ans.assign(m, 0);
  solve();
  for(int i = 0; i < m; ++i) cout << ans[m - 1 - i] << endl;
  return 0;
}

void solve() {
  ans[0] = n * (n - 1) / 2;
  uf = Unionfindw<long long>(n + 1);
  for(int i = 0; i < n; ++i) cnt[i] = 1;
  for(int i = 0; i < m - 1; ++i) {
    long long now = 0;
    if(uf.issame(v[i].fi, v[i].se)) {
      ans[i + 1] = ans[i];
      continue;
    }
    now = uf.size(v[i].fi);
    now *= uf.size(v[i].se);
    uf.uni(v[i].fi, v[i].se);
    ans[i + 1] = ans[i] - now;
  }
}

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

using namespace std;
using ll = long long;
constexpr int mod = 1e9+7;
constexpr int md = mod;
constexpr int inf = 1000000;
constexpr int def = inf;

int main(){
    string str;
    cin>>str;
    int n,e,w,s;
    n= e = w = s= 0;
    for(int i=0;i<(int)str.size();++i){
        if(str[i] == 'N') n++;
        else if(str[i] == 'E')e++;
        else if(str[i] == 'W')w++;
        else s++;
    }
    if(((n!=0)==(s!=0))&&((e!= 0)==(w!= 0))) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++)
static const long long INF = 1000000;
using p = pair<int,int>;

int main(){
    string s;
    cin >> s;
    if (s == "ABC"){
        cout << "ARC" << endl;
        return 0;
    }
    else {
        cout << "ABC" << endl;
        return 0;
    }
}

Measured memory_bytes: 3600
#include "bits/stdc++.h"

using namespace std;

//int N,M,K,L,R,H,W;
long long int N,M,K,L,R,H,W;

//const long long int MOD=1000000007;
//const int MOD=1000000007;
const int MOD=998244353;
//const long long int MOD=998244353;


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	while(cin>>H>>W,H){
		vector<int>h(H);
		vector<int>w(W);
		for(auto &i:h)cin>>i;
		for(auto &i:w)cin>>i;
		vector<int>hnum(21);
		vector<int>wnum(21);
		for(auto i:h)hnum[i]++;
		for(auto i:w)wnum[i]++;
		int ans=0;
		for(int i=1;i<=20;i++){
			ans+=max(hnum[i],wnum[i])*i;
		}
		cout<<ans<<endl;
	}
	return 0;
}



Measured memory_bytes: 3128
#include <algorithm>
#include <array>
#include <climits>
#include <cmath>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> d(n); repeat (i, n) scanf("%d", &d[i]);
    // solve
    array<int, 13> cnt = {};
    cnt[0] += 1;
    for (int d_i : d) cnt[d_i] += 1;
    int max_s = -1;
    repeat (pred, (1 << 11)) {
        array<bool, 24> used = {};
        int s = INT_MAX;
        repeat (i, 13) if (cnt[i]) {
            if (i == 0 or i == 12) {
                used[i] = true;
                if (cnt[i] >= 2) {
                    s = 0;
                }
            } else {
                if (cnt[i] == 1) {
                    used[pred & (1 << (i - 1)) ? i : 24 - i] = true;
                } else if (cnt[i] == 2) {
                    used[i] = used[24 - i] = true;
                } else {
                    s = 0;
                }
            }
        }
        repeat (i, 24) if (used[i]) {
            repeat (j, i) if (used[j]) {
                setmin(s, min(abs(i - j), 24 - abs(i - j)));
            }
        }
        setmax(max_s, s);
    }
    // output
    printf("%d\n", max_s);
    return 0;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Map;
import java.util.Scanner;
import java.util.HashMap;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ThisMessageWillSelf solver = new ThisMessageWillSelf();
        solver.solve(1, in, out);
        out.close();
    }

    static class ThisMessageWillSelf {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int[] tall = new int[n + 1];

            long result = 0;

            Map<Integer, Integer> p = new HashMap<>();
            for (int i = 1; i <= n; i++) {
                tall[i] = in.nextInt();

                int key = i + tall[i];
                p.put(key, p.getOrDefault(key, 0) + 1);

            }

            for (int i = 1; i <= n; i++) {
                if (p.containsKey(i - tall[i])) {
                    result += p.get(i - tall[i]);
                }
            }
            out.append(String.valueOf(result));
        }

    }
}



Measured memory_bytes: 70368
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

struct Edge {
	ll to, r, c;
	Edge* ori;
	Edge* rev;
	Edge(ll T, ll R, ll C)
	{
		to = T, r = R, c = C;
	}
};
vector<Edge *> v[102];
void addedge(int f, int t, ll r, ll c)
{
	Edge* ori = new Edge(t, r, c);
	Edge* rev = new Edge(f, 0, -c);
	ori->rev = rev;
	rev->rev = ori;
	v[f].push_back(ori);
	v[t].push_back(rev);
}
const int S = 0, T = 101;
int level[102],work[102];
bool bfs() {
	MEM_1(level);
	level[S] = 0;
	queue<int> q;
	q.push(S);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (auto& nn : v[x]) {
			int next = nn->to;
			if (level[next] == -1 && nn->r > 0) {
				level[next] = level[x] + 1;
				q.push(next);
			}
		}
	}
	return level[T] != -1;
}
ll dfs(int N, int des, ll flow) {
	if (N == des) return flow;

	for (int &i = work[N]; i<v[N].size(); i++) {
		int next = v[N][i]->to;
		if (level[next] == level[N] + 1 && v[N][i]->r > 0) {
			ll df = dfs(next, des, min(v[N][i]->r, flow));
			if (df > 0) {
				v[N][i]->r -= df;
				v[N][i]->rev->r += df;
				return df;
			}
		}
	}
	return 0;
}
int main() {
	int n;
	scanf("%d",&n);
	ll sum=0;
	fup(i,1,n,1)
	{
		ll x;
		scanf("%lld",&x);
		if(x>=0)
		{
			sum+=x;
			addedge(i,T,x,0);
		}
		else
		{
			addedge(S,i,-x,0);
		}
	}
	fup(i,1,n,1)
		fup(j,i+i,n,i)
		addedge(i,j,INF,0);
	ll ans=0;
	while (bfs())
	{
		MEM0(work);
		while (1)
		{
			ll f = dfs(S, T, INF);
			if (f == 0)break;
			ans += f;
		}
	}
	printf("%lld",sum-ans);
}

Measured memory_bytes: 256
loop{
  h, w = gets.split.map &:to_i
  break if h.zero? && w.zero?
  if w == 1
    e = ''
    o = ''
  else
    e = (['#'] * (w / 2)).join('.') + '.'
    o = (['.'] * (w / 2)).join('#') + '#'
  end
  
  if w.odd?
    e += '#'
    o += '.'
  end
  h.times{|i| puts i.even? ? e : o}
  puts
}

Measured memory_bytes: 8704
#include"bits/stdc++.h"


#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(int x = (l);x<=(u);x++)
#define RREP(x,l,u) for(int x = (l);x>=(u);x--)
#define mst(x,a) memset(x,a,sizeof(x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define se second
#define fi first
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define cl(x) x.clear()

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;

const int maxn = 1000010;
const int mod = 1e9+7;
const int MAX = 1000000010;
const double eps = 1e-6;
const double PI = acos(-1);

template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}

template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);}
template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}
template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}
template<typename A,typename B> inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;}
template<typename A,typename B> inline A fexp(A x,B p,A mo){A ans=1;for(;p;p>>=1,x=1LL*x*x%mo)if(p&1)ans=1LL*ans*x%mo;return ans;}

int n;

int fac[maxn];

int C(int n,int k){
	if(n<k)return 0;
	return (ll)fac[n]*fexp(fac[k],mod-2)%mod*fexp(fac[n-k],mod-2)%mod;
}

int main(){
	read(n);
	fac[0]=1;REP(i,1,n)fac[i]=(ll)fac[i-1]*i%mod;
	int ans=0;
	REP(i,0,n-1)ans=((ll)C(i-1,n-i-1)*fac[i]%mod*fac[n-i-1]+ans)%mod;
	ans=((ll)fac[n-1]*n-ans+mod)%mod;
	iout(ans);
	return 0;
}


Measured memory_bytes: 4224
#include <iostream>
#include<string>
#include<math.h>
using namespace std;


int main(){
    int A,B,C,X,Y;
    cin >> A >> B >> C >> X >> Y;
    int money=0;
    if(A+B>2*C){
        
        if(X>Y){
            money+=C*Y*2;
            X-=Y;
            Y=0;
            if(A>2*C){
                money+=X*2*C;
            }else{
                money+=X*A;
            }
        }else{
            money+=C*X*2;
            Y-=X;
            X=0;
            if(B>2*C){
                money+=Y*2*C;
            }else{
                money+=Y*B;
            }
        }
    }else{
        money+=A*X + B*Y;
    }
    cout << money;
	return 0;
}

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

bool compare( pair<int,int> a , pair<int,int> b)
{
    return a.second > b.second;
}

int main()
{
   int n;
   cin>>n;
   map<string , vector<pair<int,int>> > m;

   for(int i=1;i<=n;i++)
   {
       string city;
       cin>>city;
       int rating;
       cin>>rating;
       m[city].push_back( make_pair(i,rating ) );
   }
   auto it = m.begin();
   vector<string> cities;
   while( it!= m.end())
   {
       cities.push_back(it->first);
       it++;
   }
   sort( cities.begin() , cities.end() );
    for(int i=0;i<cities.size() ;i++)
    {
       sort(  m[cities[i]].begin() ,m[cities[i]].end() , compare );
       for(int j=0;j<m[cities[i]].size() ;j++)
       {
           cout<<m[ cities[i] ][j].first<<endl;
       }
    }

}

Measured memory_bytes: 3608
MOD = 10 ** 9 + 7


def phi(n):
    r = n
    i = 2
    while i * i <= n:
        if n % i == 0:
            r -= r // i
            while n % i == 0:
                n //= i
        i += 1
    if n > 1:
        r -= r // n
    return r


n, k = map(int, input().split())
ans = 0
for i in range(1, k + 1):
    ans += phi(i) * pow(k // i, n, MOD)
print(ans % MOD)


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

int main() {
    int R, G, B, N;
    cin >> R >> G >> B >> N;

    ll ans = 0;
    rep(r, 3001) rep(g, 3001) {
        int bB = N - r * R - g * G;
        if (bB >= 0 && bB % B == 0) ans++;
    }

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


Measured memory_bytes: 256
'use strict';
const p = s => console.log(s);
// let a,b,c,d;
// [a,b,c,d] = input[0].trim().split(" ").map(i => parseInt(i));

function main(input) {

  let a,b,h,m;
  [a,b,h,m] = input[0].trim().split(" ").map(i => parseInt(i));

  let ans = Math.sqrt(a*a + b*b - 2*a*b*Math.cos(2*Math.PI*(h/12 + (m/60)/12 - (m/60))));

  p(ans);

}
main(require('fs').readFileSync('/dev/stdin', 'utf8').trim().split("\n"));


Measured memory_bytes: 29816
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<list>

#define endl "\n"
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;

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

    sort(a.begin(),a.end());
    
    vector<int> yakusu;
    for(int i=1;i*i<=a[0];i++){
        if(a[0]%i == 0){
            yakusu.push_back(i);
            yakusu.push_back(a[0]/i);
        }
    }

    sort(yakusu.begin(),yakusu.end());

    int ans = 0;

    bool ok = true;
    for(int i=yakusu.size()-1;i>=0;i--){
        ok = true;
        for(int j=1;j<n;j++){
            if(a[j] % yakusu[i] != 0){
                ok = false;
                break;
            }
        }
        if(ok){
            ans = yakusu[i];
            break;
        }
    }

    cout<<ans<<endl;
}

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

int main(){
	int A, B, C;
	cin >> A >> B >> C;
	int a = A + B;
	int b = A - B;
	int c = A * B;
	
	int ans = max(max(a, b), c);
	cout << ans << endl;
}

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

template<int MOD>
struct mod_int {
	static const int mod = MOD;
	unsigned x;
	mod_int() : x(0) { }
	mod_int(int sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	mod_int(long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }

	mod_int &operator+=(mod_int that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
	mod_int &operator-=(mod_int that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	mod_int &operator*=(mod_int that) { x = (unsigned long long)x * that.x % MOD; return *this; }
	mod_int &operator/=(mod_int that) { return *this *= that.inverse(); }

	mod_int operator+(mod_int that) const { return mod_int(*this) += that; }
	mod_int operator-(mod_int that) const { return mod_int(*this) -= that; }
	mod_int operator*(mod_int that) const { return mod_int(*this) *= that; }
	mod_int operator/(mod_int that) const { return mod_int(*this) /= that; }

	mod_int inverse() const {
		long long a = x, b = MOD, u = 1, v = 0;
		while (b) {
			long long t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		return mod_int(u);
	}
};

template<int MOD>
istream& operator >> (istream& is, mod_int<MOD>& val) {
	long long x;
	is >> x; val = x;
	return is;
}

template<int MOD>
ostream& operator << (ostream& os, const mod_int<MOD>& val) {
	os << val.get();
	return os;
}

using mint = mod_int<998244353>;

const int MAX = 2e6;

mint fac[MAX + 1];
mint rfac[MAX + 1];

void init() {
	fac[0] = 1;
	for (int i = 1; i <= MAX; i++) {
		fac[i] = fac[i - 1] * i;
	}
	rfac[MAX] = fac[MAX].inverse();
	for (int i = MAX; i >= 1; i--) {
		rfac[i - 1] = rfac[i] * i;
	}
}

mint nPr(int n, int r) {
	return r < 0 || n < r ? 0 : fac[n] * rfac[n - r];
}

mint nCr(int n, int r) {
	return r < 0 || n < r ? 0 : fac[n] * rfac[n - r] * rfac[r];
}

mint nHr(int n, int r) {
	return r == 0 ? 1 : nCr(n + r - 1, r);
}

int main()
{
	init();
	int N;
	ll A, B, K;
	cin >> N >> A >> B >> K;
	mint res = 0;
	for (int i = 0; i <= N; i++) if (i * A <= K && (K - i * A) % B == 0) {
		int j = (K - i * A) / B;
		res += nCr(N, i) * nCr(N, j);
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 16000
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr long double EPS = 1e-15;
const long double PI = acos(-1);
constexpr int inf = 2e9;
constexpr ll INF = 2e18;
constexpr ll MOD = 1e9+7;
constexpr ll MOD1 = 998244353;
typedef pair<ll,ll> P;

//#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
//#define mp make_pair

pair<ll,ll> a[100010];

void solve() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n,m;
    cin >> n >> m;
    REP(i,n) {
        cin >> a[i].fi >> a[i].se;
    }
    sort(a,a+n);
    int p = 0;
    priority_queue<int> pq;
    ll ans = 0;
    for (int d = m - 1; d >= 0; d--) {
        while (p < n && a[p].fi + d <= m) {
            pq.push(a[p].se);
            p++;
        }
        if (!pq.empty()) {
            ans += pq.top();
            pq.pop();
        }
    }
    cout << ans << endl;
}

int main(int argc, char *argv[]){

    /* Regular */
    int case_num = 1;
    if (argc > 1 && stoi(argv[1])) cin >> case_num;
    REP(case_no, case_num) {
      cerr << endl << "case " << case_no + 1 << endl;
      solve();
    }

    // /* AOJ */
    // solve();
    return 0;
}

Measured memory_bytes: 2428
N = int(input())
S = input()
ans = 0
for i in range(1, N):
    head = set(S[:i])
    tail = set(S[i:])
    tmp_sum = 0
    for c in head:
        if c in tail:
            tmp_sum += 1

    ans = max(ans, tmp_sum)

print(ans)


Measured memory_bytes: 39664
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod 1000000009
#define tc(t) 			int t;cin >> t;while(t--)
#define for0(i , n)		for(int i=0;i<n;i++)
#define loop(i , a, b)	for(int i=a;i<=b;i++)
#define endl '\n'

int n;
int a[100005],b[100005],c[100005];
int dp[100005][4];

int vacation(int ind,int fl){
	if(ind >= n){
		return 0;
	}

	if(dp[ind][fl] != -1){
		return dp[ind][fl];
	}

	int ans = 0;

	if(fl == 0){
		int c1 = a[ind] + vacation(ind+1,1);
		int c2 = b[ind] + vacation(ind+1,2);
		int c3 = c[ind] + vacation(ind+1,3);	
		ans+=max(c1,max(c2,c3));
	}else if(fl == 1){
		int c2 = b[ind]+vacation(ind+1,2);
		int c3 = c[ind]+vacation(ind+1,3);
		ans += max(c2,c3); 
	}else if(fl == 2){
		int c1 = a[ind]+vacation(ind+1,1);
		int c3 = c[ind]+vacation(ind+1,3);
		ans += max(c1,c3); 		
	}else if(fl == 3){
		int c2 = b[ind]+vacation(ind+1,2);
		int c1 = a[ind]+vacation(ind+1,1);
		ans += max(c2,c1); 		
	}

	return dp[ind][fl] = ans;
}

signed main() {

	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
#ifndef ONLINE_JUDGE
	freopen("input.txt" , "r" , stdin);
	freopen("output.txt" , "w" , stdout);
#endif

	cin >> n;

	for0(i,n){
		cin >> a[i] >> b[i] >> c[i];
	}

	memset(dp,-1,sizeof(dp));

	cout << vacation(0,0);

	return 0;
}

Measured memory_bytes: 15276
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
   int x; cin>>x;
   int a500=x/500;
   int a5=(x%500)/5;
   cout<<a500*1000+a5*5<<endl;
   return 0;
}



Measured memory_bytes: 256
import java.util.*;
import java.math.*;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] data = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

    int n = sc.nextInt();
    System.out.println(data[n-1]);

  }
}


Measured memory_bytes: 21204
/*"Everything in the universe is balanced. Every disappointment
   you face in life will be balanced by something good for you!
                Keep going, never give up."            */

#include "bits/stdc++.h"
using namespace std;


#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ordered_set<int>  os;
#define up_bound(i) os.order_of_key(i) << endl; // the number of elements in the os less than i
#define access_idx(i) *os.find_by_order(i) // print the i-th smallest number in os(0-based)

typedef double f80;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){uniform_int_distribution<int> uid(l, r); return uid(rng); }

#define ll long long int
#define ld double 
#define rep(i,a,b) for(int i=a; i<=b; ++i)
#define repd(i,a,b) for(int i=a; i>=b; --i)
#define deb cerr << "Line no." << __LINE__
#define nl '\n'
#define pb push_back
#define all(a) a.begin(),a.end()
#define P pair<ll,ll> 
#define F first
#define S second
const ll p_mod=9999999999999983;
const long double pi = 3.14159265358979323;
const ll N=1e6+9;
const ll mod=1e9+7;
ll powerk(ll x, ll y);
ll mul(ll x, ll y);
ll add(ll x, ll y);
ll sub(ll x, ll y);

ll a[N],dp[101][100005];

void solve()
{    
  ll n,m;
  cin>>n>>m;
  rep(i,1,n)cin>>a[i];
  rep(i,0,m)dp[0][i]=1;
  rep(i,1,n)
  {
  	rep(j,0,m)
  	{
  		if(j<=a[i])
  		dp[i][j] = add(dp[i][j],dp[i-1][j]);
  		else{
  			dp[i][j] = add(dp[i][j],dp[i-1][j]-dp[i-1][j-a[i]-1]);
  		} 
  		dp[i][j] = add(dp[i][j],dp[i][j-1]);
  		//cout<<dp[i][j]<<" ";
  	}
  	//cout<<nl;
  }
  cout<<sub(dp[n][m],dp[n][m-1]);

}


int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll t=1;
    //pre();
    //cin>>t;
    while(t--)
    {
      solve();
    }  
}
ll mul(ll x, ll y){return (x*y)%mod;}
ll add(ll x, ll y){return (x+y)%mod;}
ll sub(ll x, ll y){return (x-y+mod)%mod;}
ll powerk(ll x, ll y)
{
  if(y==0)return 1;
  if(y==1)return x%mod;
  if(y&1)
    return ((powerk((x*x)%mod, y/2)%mod)*x)%mod;
  else return powerk((x*x)%mod,y/2)%mod;
}

// Xorawar

Measured memory_bytes: 80128
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,maxn;
char s[102],t[102];
int main()
{
	scanf("%d%s%s",&n,s,t);
	for(int i=0;i<n;i++)
		if(s[i]==t[0])
		{
			int l=0;
			for(int j=0;j<n;j++)
				if(t[j]==s[j+i])l++;
				else	break;
			maxn=max(maxn,l);
		}
	printf("%d",n*2-maxn);
}

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

long long n,k,a[2010],b[2010][2],c[2010],ans,tmp;

int main(){
    cin>>n>>k;
    for(long long i=0;i<n;i++)cin>>a[i];
    for(long long i=0;i<n;i++){
        for(long long j=0;j<n;j++){
            if(a[j]<a[i]){
                if(j<i)b[i][0]++;
                else if(j>i) b[i][1]++;
            }
        }
    }
    for(long long i=0;i<n;i++){
        tmp=k*(k-1)/2%1000000007*(b[i][0]+b[i][1])+k*b[i][1]%1000000007;
        ans+=tmp;
        ans%=1000000007;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
s = str(input())

slist = []
for i in s:
    slist.append(int(i))

x0 = 753
min = 999

for i in range(len(slist)-2):
    x = int(s[i:i+3])
    sabun = abs(x - x0)
    if min > sabun:
        min = sabun

print(min)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int h, w, k; scanf("%d%d%d", &h, &w, &k);
	std::vector<std::string> s(h);
	for(int i = 0; i < h; i++) cin >> s[i];

	int cnt = 1;
	auto ans = make_v<int>(h, w);
	for(int i = 0; i < w; i++) {
		bool exist = false;
		for(int j = 0; j < h; j++) exist |= (s[j][i] == '#');

		if(exist) {
			for(int j = 0; j < h; j++) {
				ans[j][i] = cnt;

				cnt += (s[j][i] == '#');
			}
			cnt--;

			for(int j = h - 1; j >= 0; j--) {
				if(s[j][i] == '#') break;

				ans[j][i] = cnt;
			}
			cnt++;
		} else {
			for(int j = 0; j < h; j++) {
				if(i) ans[j][i] = ans[j][i - 1];
				else ans[j][i] = -1;
			}
		}
	}
	for(int i = w - 2; i >= 0; i--) {
		if(ans[0][i] != -1) continue;

		for(int j = 0; j < h; j++) ans[j][i] = ans[j][i + 1];
	}
	
	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) printf("%d ", ans[i][j]);
		printf("\n");
	}
	return 0;
}


Measured memory_bytes: 1280
s = input()
if len(s) != 3:
	print('length')
	exit()

s_list = list(s)

for x in s_list:
	if int(x) < 0 or int(x) > 1:
		exit()

marble = 0
for x in s_list:
	if int(x) == 1:
		marble += 1

print(marble)


Measured memory_bytes: 2940
// g++ macro.cpp -std=c++14
#include <bits/stdc++.h> //STL include
typedef long long ll;// long long int
const ll INF = 10000000000;//INFinity
using namespace std;//namespace

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}//transform
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//#define int long long // yabai

#define dump(x)  cout << #x << " = " << (x) << endl;// debug cout

#define FOR(i,a,b) for(int i=(a);i<(b);++i)// for macro
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)

#define ALL(obj) (obj).begin(),(obj).end()// iterator

#define pb(a) push_back(a)//push_back
#define mp make_pair// make_pair


int main(){

    int n,m;
    cin>>n>>m;
    vector<pair<int,int>> ab(m);
    REP(i,m)cin>>ab[i].first>>ab[i].second;
    int sum=0;
    REP(i,m){
        vector<pair<int,int>> cp=ab;
        cp.erase(cp.begin()+i);
        vector<bool> graph(n,false);
        graph[0]=true;
        REP(i,m){
            for(auto p:cp){
                if(graph[p.first-1])graph[p.second-1]=true;
                if(graph[p.second-1])graph[p.first-1]=true;
            }
        }
        for(auto p:graph)if(!p){++sum;break;}
    }
    cout<<sum<<endl;

    return 0;
}


Measured memory_bytes: 256