akhauriyash/Code-Regression huggingface dataset:
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>
#include <cassert>
#include <random>

#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll conbinationMemo[100][100];

void cmemoInit(){
    rep(i, 100){
        rep(j, 100){
            conbinationMemo[i][j] = -1;
        }
    }
}
 
ll nCr(ll n, ll r){
    if(conbinationMemo[n][r] != -1) return conbinationMemo[n][r];
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return conbinationMemo[n][r] = (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
//-----------------------ここから-----------
ll n, m;
pair<ll,ll> calc(vector<int> &removed, vector<vector<ll>> &a){

    vector<ll> cnt(m, 0);

    rep(i, n){
        rep(j, m){
            if(removed[a[i][j]]) continue;
            cnt[a[i][j]]++;
            break;
        }
    }

    ll maidx = 0;
    ll ma = 0;
    rep(i, m){
        if(removed[i]) continue;
        if(ma < cnt[i]){
            maidx = i;
            ma = cnt[i];
        }
    }

    return {ma, maidx};
}
bool check(vector<int> &removed){
    bool res = false;;
    rep(i, m){
        if(!removed[i]){
            res = true;
        }
    }

    return res;
}
int main(void){
    cin >> n >> m;

    vector<vector<ll>> a(n, vector<ll>(m));
    rep(i, n){
        rep(j, m){
            cin >> a[i][j];
            a[i][j]--;
        }
    }
    ll ans = INF;
    vector<int> removed(m, 0);
    pair<ll,ll> result = calc(removed, a);
    ans = min(ans, result.first);
    removed[result.second] = 1;

    while(check(removed)){
        result = calc(removed, a);
        ans = min(ans, result.first);
        removed[result.second] = 1;
    }
    cout << ans << endl;
    return 0;

}   

Measured memory_bytes: 4336
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define debug(x) cerr<<#x<<":"<<x<<endl
const int maxn=(int)1e6+5;
typedef long long ll;
const ll MOD=(ll)1e9+7;
//等价于n拆分成小于等于k个正整数的方案数
ll dp[1005][1005];//dp[i][j] j拆成i个非负数

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,k;cin>>n>>k;
    n-=k;
    for(int i=0;i<=k;i++){
        dp[i][0]=1;
        for(int j=1;j<=n;j++){
            if(j-i>=0)
            dp[i][j]+=dp[i][j-i];//每个数加1？

            if(i-1>=0)
            dp[i][j]+=dp[i-1][j];//拆出个0
            
            dp[i][j]%=MOD;
        }
    }
    if(n>=0)cout<<dp[k][n]<<endl;
    else cout<<0<<endl;
}


Measured memory_bytes: 7376
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define pb push_back

main()
{
    //freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
	int n,x;
	cin>>n>>x;
	int arr[n];
	for(int i=0;i<n;i++)
		cin>>arr[i];

	int dp[n+1];
	dp[0]=0;
	for(int i=1;i<=n;i++)
		dp[i]=dp[i-1]+arr[i-1];

	int ans=0;
	for(int i:dp)
	{
		if(i<=x)
			ans++;
	}
	
	cout<<ans;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
s = 'abcdefghijklmnopqrstuvwxyz'


def calc(x, i):
  target = x - 26 ** i
  if (target <= 0):
    return (x, i)
  else:
    return calc(target, i + 1)


target, index = calc(n, 1)
target -= 1
base26 = [0] * index
for i in range(index):
  tmp, target = divmod(target, 26 ** (index - i - 1))
  base26[i] = tmp
ans = ''
for i in base26:
  ans += s[i]
print(ans)

Measured memory_bytes: 61932
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;

struct edge{int to,cost;};
struct dijkstra
{
  using P=pair<int,int>;
  priority_queue<P,vector<P>,greater<P>> q;
  vector<vector<edge>>ed;
  vector<int>dist;
  int sz;
  dijkstra(int size){
    sz=size;
    ed.resize(size);
  }
  void reset(){
    dist.assign(sz,-1);
    q=priority_queue<P,vector<P>,greater<P>>();
  }
  void ae(int from,int to,int cost){
    ed[from].push_back({to,cost});
  }
  int cal(int start,int end=0){
    reset();
    q.push({0,start});
    while(!q.empty()){
      P tp=q.top();q.pop();
      if(dist[tp.second]!=-1)continue;
      dist[tp.second]=tp.first;
      for(auto nn:ed[tp.second]){
        if(dist[nn.to]!=-1)continue;
        q.push({nn.cost+tp.first,nn.to});
      }
    }
    return dist[end];
  }
  int getd(int end){
    return dist[end];
  }
};
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int k;cin>>k;
  dijkstra dj(k),dj2(k);
  rep(i,k)
  {
    dj.ae(i,(i+1)%k,1);
    dj2.ae((i+1)%k,i,1);

    dj.ae(i,i*10%k,0);
    dj2.ae(i*10%k,i,0);

  }
  int res=1e9;

  dj.cal(0);
  dj2.cal(0);
  rep(i,k-1)
  {
    chmin(res,dj.getd(i+1)+dj2.getd(i+1));
  }
  cout<<res<<endl;


  return 0;

}


Measured memory_bytes: 13948
#include <bits/stdc++.h>
#define ll long long
#define f(i, a, b) for(ll i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
ll findSubarraySum(ll arr[], ll n, ll sum = 0) 
{
    unordered_map<ll, ll> prevSum;
    ll res = 0;
    ll currsum = 0;
    for (ll i = 0; i < n; i++)
    {
        currsum += arr[i];
        if (currsum == sum) res++;
        if (prevSum.find(currsum - sum) != prevSum.end()) res += (prevSum[currsum - sum]);
        prevSum[currsum]++;
    }
    return res; 
} 
ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
  
ll findGCD(ll arr[], ll n) 
{ 
    ll result = arr[0]; 
    for (ll i = 1; i < n; i++)
        result = gcd(arr[i], result); 
  
    return result; 
} 
ll powmp(ll x, ll y, ll p) 
{ 
    ll res = 1;     x = x % p;   
    while (y > 0) 
    {  
        if (y & 1)  res = (res*x) % p; 
        y = y>>1; 
        x = (x*x) % p;   
    } 
    return res; 
} 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        // If the element is present at the middle 
        // itself 
        if (arr[mid] == x) 
            return mid; 
  
        // If element is smaller than mid, then 
        // it can only be present in left subarray 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        // Else the element can only be present 
        // in right subarray 
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    // We reach here when element is not 
    // present in array 
    return -1; 
} 

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    string s; cin>>s;
    ll ans=0;
    ll n=s.length();
    ll a[n+1];
    ll prevmax=0;
    f(i,0,n)
    {
        ll c=0;
        while(s[i]=='<')
        {
            i++;c++;
        }
        if(c>=1) 
            {i--;
                    ans+=c*(c+1)/2;
                    prevmax=c;}
        c=0;
        while(s[i]=='>')
        {
            i++;c++;
        }
        if(c>=1) {i--;
                ans+=c*(c+1)/2;
                ans-=min(prevmax, c);
                prevmax=c;}
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1172
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
    int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n,q;cin>>n>>q;
    string s;cin>>s;
    vector<ll> cnt(n,0);
    for(ll i=0;i<n;i++){
        cnt[i]=(i>0?cnt[i-1]:0);
        if(i<n-1 && s[i]=='A' && s[i+1]=='C')cnt[i]++;
    }
    while(q--){
        ll l,r;cin>>l>>r;
        l--;r--;
        ll ans = cnt[r-1] - (l>0?cnt[l-1]:0);
        cout<<ans<<"\n";
    }
}

Measured memory_bytes: 1872
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define UNIQUE(v) { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); }
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return true;} return false; }
template<class T> bool chmin(T &a, const T &b) {if (a > b) {a = b; return true;} return false; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) (q ? "Yes" : "No")
#define YES(q) (q ? "YES" : "NO")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) { cerr << "[DEBUG] " #q ": ["; REP(dumpall_i, (q).size()) { cerr << q[dumpall_i] << (dumpall_i == (q).size() - 1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; }
template<class T> T gcd(const T &a, const T &b) { return a < b ? gcd(b, a) : b ? gcd(b, a % b) : a; }
template<class T> T lcm(const T &a, const T &b) { return a / gcd(a, b) * b; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
using  ll = long long;
using ull = unsigned long long;
using  ld = long double;
using namespace std;

// モジュール


// 処理内容
int main() {
    
    ll n, a, b; cin >> n >> a >> b;

    cout << min(n * a, b) << endl;
    
}

Measured memory_bytes: 764
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N, K = map(int, input().split())

    if N % K == 0:
        print(0)
    else:
        i = N // K
        print(min(abs(N - i * K), abs(N - (i+1) * K)))

if __name__ == '__main__':
    main()


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

int main() {
  int N, K;
  cin >> N >> K;
  set<int> s;
  for (int i = 0; i < K; i++) {
    int d;
    cin >> d;
    for (int j = 0; j < d; j++) {
      int x;
      cin >> x;
      s.insert(x);
    }
  }
  int n = s.size();
  cout << N-n << endl;
}

Measured memory_bytes: 3628
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container, std.format, std.datetime;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] lreads(T = long)(long n){return generate(()=>readln.chomp.to!T()).take(n).array();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);
// dfmt on

void main()
{
    auto S = sread();
    bool g(string s)
    {
        foreach (i; 0 .. s.length / 2)
            if (s[i] != s[$ - i - 1])
                return false;
        // writeln(s);
        return true;
    }

    bool f()
    {
        return g(S) && g(S[0 .. $ / 2]) && g(S[($ + 1) / 2 .. $]);
    }

    writeln(f() ? "Yes" : "No");
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        int w = scn.nextInt();
        int[][] wav = new int[n+1][3]; //1 weight 2 value
        for(int i=1;i<=n;i++){
            wav[i][1] = scn.nextInt();
            wav[i][2] = scn.nextInt();
        }
        // System.out.println(1e5+1);
        //jth col ki val using 1...ith elemnets min in how much weight
        long[][] dp = new long[n+1][(int)(1e5+1)];
        for(int i=1;i<=n;i++){
            for(int val=1;val<=(int)Math.pow(10,5);val++){
                if(i==1){
                    dp[i][val] = (wav[1][2]==val?wav[1][1]:(int)1e9+1);
                }else{
                    long o1 = wav[i][2] <= val ? dp[i-1][val-wav[i][2]] + wav[i][1] : (int)1e9;
                    long o2 = dp[i-1][val];
                    dp[i][val] = Math.min(o1,o2);
                }
            }
        }
        
        long ans = 0;
        for(int val=1;val<=(int)1e5;val++){
            if(dp[n][val]<=w){
                ans = Math.max(ans,val);
            }
        }
        System.out.println(ans);
    }
}

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


void main() {
    int n;
    scan(n);

    foreach (i ; 0 .. n) {
        string s;
        scan(s);
        solve(s);
    }
}

void solve(string s) {
    auto a = [".,!? ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    auto ss = s.group;
    string res;

    foreach (si ; ss) {
        if (si[0] == '0') continue;
        int d = si[0] - '0' - 1;

        res ~= a[d][(si[1]-1) % a[d].length];
    }

    writeln(res);
}


void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



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

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

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int n; cin>>n;
	int ret=0,cur=0; char ch;
	while(n--) {
		cin>>ch;
		if(ch=='I') cur++;
		else cur--;
		ret=max(ret,cur);
	}
	cout << ret << endl;
	return 0;
}


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

typedef struct dice_tag{
	int num[7];
} dice_t;


void north(dice_t *dice)
{
	int tmp = dice->num[1];
	dice->num[1] = dice->num[2];
	dice->num[2] = dice->num[6];
	dice->num[6] = dice->num[5];
	dice->num[5] = tmp;
}

void south(dice_t *dice)
{
	int tmp = dice->num[1];
	dice->num[1] = dice->num[5];
	dice->num[5] = dice->num[6];
	dice->num[6] = dice->num[2];
	dice->num[2] = tmp;
}

void west(dice_t *dice)
{
	int tmp = dice->num[1];
	dice->num[1] = dice->num[3];
	dice->num[3] = dice->num[6];
	dice->num[6] = dice->num[4];
	dice->num[4] = tmp;
	
}

void east(dice_t *dice)
{
	int tmp = dice->num[1];
	dice->num[1] = dice->num[4];
	dice->num[4] = dice->num[6];
	dice->num[6] = dice->num[3];
	dice->num[3] = tmp;

}

void turnRight(dice_t *dice)
{
	int tmp = dice->num[2];
	dice->num[2] = dice->num[4];
	dice->num[4] = dice->num[5];
	dice->num[5] = dice->num[3];
	dice->num[3] = tmp;
}

void keep_turn_right(dice_t *dice, int center)
{
	while(dice->num[2] != center)
	{
		turnRight(dice);
	}
	
	printf("%d\n", dice->num[3]);
}



int main(void)
{
	int q, top, center;
	dice_t dice;

	for(int i = 1; i <= 6; i++) scanf("%d", &dice.num[i]);
	scanf("%d", &q);

	for(int i = 0; i < q; i++)
	{
		scanf("%d %d", &top, &center);
		if(top == dice.num[1])
		{
			keep_turn_right(&dice, center);
		}
		else if(top == dice.num[2])
		{
			north(&dice);
			keep_turn_right(&dice, center);
		}
		else if(top == dice.num[3])
		{
			west(&dice);
			keep_turn_right(&dice, center);
		}
		else if(top == dice.num[4])
		{
			east(&dice);
			keep_turn_right(&dice, center);
		}
		else if(top == dice.num[5])
		{
			south(&dice);
			keep_turn_right(&dice, center);
		}
		else
		{
			north(&dice);
			north(&dice);
			keep_turn_right(&dice, center);
		}
		
	}

	
	
	return 0;
}


Measured memory_bytes: 3224
import java.util.*;


public class Main{
	public static void main(String[] args){
      	
      	// 値取得
    	Scanner sc = new Scanner(System.in);
      	String str = sc.next();
      	// System.out.println(str);
      	int cnt = 0;
      	// 文字列数分繰り返す
      	for(int i = 0; i < 4; i++){
      		// i文字目を取得する
      		char st = str.charAt(i);
      		// 他の文字と比較する
      		for(int j = 0; j < 4; j++){
      			char stt = str.charAt(j);
      			// 判定
	      		if (stt == st){
	      			cnt++;
	      			//System.out.println(cnt);
	    	  	}
      		}
      	}

      	if(cnt == 8){
      		System.out.println("Yes");
      	}else{
      		System.out.println("No");
      	}
    }
}

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

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

  vector<int> a(n);
  rep(i,n) cin >> a[i];

  sort(a.begin(),a.end());
  int answer = 0;
  for (int i = 1; i <= 100000; i++) {
    int itr = upper_bound(a.begin(),a.end(),i) - a.begin();
    if(itr == n/2) answer++;
  }
  cout << answer << '\n';
}


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

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  if (a == b) cout << c << endl;
  else if (a == c) cout << b << endl;
  else cout << a << endl;
  return 0;
}


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

int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i,n){
		cin >> a[i];
		a[i]--;
	}
	int cnt = 0;
	int sta = 0;
	while(1){
		sta = a[sta];
		cnt++;
		if(sta == 1){
			cout << cnt << endl;
			return 0;
		}
		if(cnt >= n+1){
            cout << -1 << endl;return 0;
        }
    }
}

Measured memory_bytes: 640
#include <stdio.h>

int main() {
    int i=0;
    int j=0;
    for(i=1; i<=9; i++){
        for(j=1; j<=9; j++){
            printf("%dx%d=%d", i, j, i*j);
            printf("\n");
        }
    }
    return 0;
}

Measured memory_bytes: 524
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int r = sc.nextInt();
        if (r < 1200)
            System.out.println("ABC");
        else if (r < 2800)
            System.out.println("ARC");
        else
            System.out.println("AGC");
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
void read(pp& x){ scanf("%d%d",&x.first, &x.second); }
void read(pll& x){ scanf("%lld%lld",&x.first, &x.second); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
void cppio(){ ios_base::sync_with_stdio(0); cin.tie(0); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define sz(x) (int)(x).size()

const int maxn = 510;
int n;
int cost[maxn][maxn];

ll dp[maxn][maxn];

ll cp[maxn][maxn];
ll gp[maxn][maxn];

int main()
{
	cppio();
	cin >> n;
	rrep(i, n) rrep(j, n) if(i != j) cin >> cost[i][j];

	rrep(i, n) rrep(j, n)
		cp[i][j] = cp[i-1][j] + cp[i][j-1] - cp[i-1][j-1] + cost[i][j];

	rrep(i, n) {
		for(int j=i+1; j<=n; ++j) {
			gp[i][j] = gp[i][j-1];
			for(int k=i; k<j; ++k) {
				gp[i][j] += cost[k][j];
			}
		}
	}

	memset(dp, 0x7f, sizeof(dp));

	dp[1][1] = 0;
	for(int i=2; i<=n; ++i)
		dp[1][i] = gp[1][i];

	auto rect = [&](int l, int r, int d, int u) -> ll {
		if(l>r || d>u) return 0;
		return cp[r][u] - cp[l-1][u] - cp[r][d-1] + cp[l-1][d-1];
	};

	rrep(l, n) {
		for(int r=l; r<=n; ++r) {
			for(int R=r+1; R<=n; ++R) {
				dp[r+1][R] = min(dp[r+1][R],
					dp[l][r] + gp[r+1][R] +
						rect(r+1, R, 1, l-1));
			}
		}
	}

/*
	rrep(i, n) {
		for(int j=i; j<=n; ++j) printf("dp[%d][%d] = %lld\n", i, j, dp[i][j]);
	}
*/

	ll ans = 1ll << 60;
	rrep(i, n) ans = min(ans, dp[i][n]);

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 7296
#include<iostream>
using namespace std;
int main()
{
	int a,b,c,x;
	int sum = 0;
	cin >> a>>  b>>c>>x;
	for (int i = 0; i <= a; i++)
	{
		for (int j = 0; j <= b; j++)
		{
			for (int e = 0; e <= c; e++)
			{
				if (i * 500 + j * 100 + e * 50 == x)
					sum++;
			}
		}
	}
	cout << sum<<endl;
	system("pause");

}

Measured memory_bytes: 504
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>

using namespace std;

int n;
int d[50];
int fib(int i) {
	if (d[i] > 0) return d[i];

	int res = fib(i - 1) + fib(i - 2);
	d[i] = res;
	return res;
}
int main() {
	d[0] = 1;
	d[1] = 1;
	cin >> n;
	cout << fib(n) << endl;
	return 0;
}

Measured memory_bytes: 1164
def checkio(numbers_array):
    return sorted(numbers_array, key=lambda x: abs(x))


n,l = map(int, input().split())
 
w_list=[]
 
for i in range(n):
    w_list.append(l+(i+1)-1)

    
w_list=checkio(w_list)
ans=0
for i in range(n-1):
    ans=ans+w_list[i+1]
#print(w_list)
print(ans)

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

#define rep(i, n) for(int i = 0; i < n; i ++)
#define ITER(c) __typeof((c).begin())
#define each(c, it) for(ITER(c) it =(c).begin(); it!=(c).end(); it++)
#define ALL(c) c.begin(), c.end()
#define mp make_pair
#define pb push_back
#define MEMSET(v, h) memset((v), h, sizeof(v))
 
using namespace std; 

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;

const int INF = 1 << 24;
const int M[] = {500, 100, 50, 10, 5, 1};

int main(void){
    for(int m, cnt; cin >> m, cnt = 0, m; cout << cnt << endl)
        rep(i, 6) while(m + M[i] <= 1000) m += M[i], cnt ++;
 
    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
    ll N, K;
    cin >> N >> K;
    vector<int> A(N+1);
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    vector<int> v;
    map<int, int> mp;
    int x = 1;
    while (1) {
        v.push_back(x);
        mp[x] = v.size()-1;
        x = A[x];
        if (mp.find(x) != mp.end()) {
            break;
        }
    }
    int a = mp[x], b = v.size();
    if (K < b) {
        cout << v[K] << endl;
        return 0;
    }
    K -= a;
    K %= b-a;
    K += a;
    cout << v[K] << endl;
}

Measured memory_bytes: 13932
#include <bits/stdc++.h>
using namespace std;
long long n, m, i, j, k, a, b;
int main(){
	cin >> n >> m >> i >> j;
    a = n*i>n*j ? n*i:n*j;
  	b = m*i>m*j ? m*i:m*j;
  	a = a>b ? a:b;
    cout << a;
}

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

#define MAX (100005)

typedef struct pp{
    char name[100];
    int a;
}BOX;

int head,tail,n;
BOX Q[MAX+1];

void initialize(){
    head=tail=0;
}

int isEmpty(){
    return head==tail;
}

int isFull(){
    return head==(tail+1)%MAX;
}

void enqueue(BOX *x){
    if(isFull())return;
    Q[tail]=*x;
    if(tail+1==MAX)tail=0;
    else tail++;
}

BOX dequeue(){
    BOX x;
    x=Q[head];
    if(head+1==MAX)head=0;
    else head++;
    return x;
}

int main(void){
    int sum=0;
    int q;
    BOX x;
    initialize();
    scanf("%d %d",&n,&q);
    for(int i=0;i<n;i++){
        scanf("%s",x.name);
        scanf("%d",&(x.a));
        enqueue(&x);
    }
    while(!(isEmpty())){
        x=dequeue();
        if(x.a<=q){
            sum+=x.a;
            printf("%s %d\n",x.name,sum);
        }else{
            if(!(isFull())){
                x.a-=q;
                sum+=q;
                enqueue(&x);
            }
        }
    }
    return 0;
}



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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int res = 0;
	int k;
	cin>>k;
	for (int i = 1; i <= k; ++i){
		for (int j = 1; j <= k; ++j){
			for (int l = 1; l <= k; ++l){
				res += __gcd(i,__gcd(j,l));
			}
		}
	}
	cout<<res<<endl;
}


Measured memory_bytes: 3640
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template <class M>
struct LazySegmentTree{
    using T = typename M::T;
    using L = typename M::L;
    int sz, height{};
    vector<T> seg; vector<L> lazy;
    explicit LazySegmentTree(int n) {
        sz = 1;
        while(sz < n) sz <<= 1, height++;
        seg.assign(2*sz, M::e());
        lazy.assign(2*sz, M::l());
    }

    void set(int k, const T &x){
        seg[k + sz] = x;
    }

    void build(){
        for (int i = sz-1; i > 0; --i) seg[i] = M::f(seg[2*i], seg[2*i+1]);
    }

    T reflect(int k){ return lazy[k] == M::l() ? seg[k] : M::g(seg[k], lazy[k]); }

    void eval(int k){
        if(lazy[k] == M::l()) return;
        lazy[(k<<1)|0] = M::h(lazy[(k<<1)|0], lazy[k]);
        lazy[(k<<1)|1] = M::h(lazy[(k<<1)|1], lazy[k]);
        seg[k] = reflect(k);
        lazy[k] = M::l();
    }
    void thrust(int k){ for (int i = height; i; --i) eval(k>>i); }
    void recalc(int k) { while(k >>= 1) seg[k] = M::f(reflect((k<<1)|0), reflect((k<<1)|1));}
    void update(int a, int b, const L &x){
        thrust(a += sz); thrust(b += sz-1);
        for (int l = a, r = b+1;l < r; l >>=1, r >>= 1) {
            if(l&1) lazy[l] = M::h(lazy[l], x), l++;
            if(r&1) --r, lazy[r] = M::h(lazy[r], x);
        }
        recalc(a);
        recalc(b);
    }

    T query(int a, int b){ // [l, r)
        thrust(a += sz);
        thrust(b += sz-1);
        T ll = M::e(), rr = M::e();
        for(int l = a, r = b+1; l < r; l >>=1, r>>=1) {
            if (l & 1) ll = M::f(ll, reflect(l++));
            if (r & 1) rr = M::f(reflect(--r), rr);
        }
        return M::f(ll, rr);
    }

    T operator[](const int &k) const { // 0-indexed
        return seg[k + sz];
    }
};

struct Monoid{
    using T = int;
    using L = int;
    static T f(T a, T b) { return min(a, b); }
    static T g(T a, L b) {
        if(b == e()) return a; else return b;
    }
    static L h(L a, L b) {
        if(b == e()) return a; else return b;
    }
    static T e() { return INT32_MAX; }
    static L l() { return INT32_MAX; }
};

int main() {
    int n, q;
    cin >> n >> q;
    LazySegmentTree<Monoid> seg(n);
    for (int i = 0; i < q; ++i) {
        int c;
        scanf("%d", &c);
        if(c == 0){
            int s, t, x;
            scanf("%d %d %d", &s, &t, &x);
            seg.update(s, t+1, x);
        }else {
            int x, y;
            scanf("%d %d", &x, &y);
            printf("%d\n", seg.query(x, y+1));
        }
    }
    return 0;
}


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

using namespace std;

int main() {
	int n;
	string s;
	cin >> n >> s;

	string ans = "No";
	if (n % 2 == 0) {
		string s1 = s.substr(0, n / 2);
		string s2 = s.substr(n / 2);

		if (s1 == s2) {
			ans = "Yes";
		}
	}

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


Measured memory_bytes: 256
using System;
using static System.Console;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

class Program
{
    static void Main()
    {
        var line1 = MyUtil.ReadlongArray();
        int hosekiCount = (int)line1[0];
        int sosaCount = (int)line1[1];

        long[] hoseki = MyUtil.ReadlongArray();

        var saidai = 0l;

        for (int right = 0; right <= sosaCount; right++)
        {
            for (int left = 0; right + left <= sosaCount; left++)
            {
                if (right + left > hosekiCount)
                    continue;

                List<long> hos = new List<long>();
                for (int i = 0; i < right; i++)
                {
                    hos.Add(hoseki[i]);
                }

                for (int i = 0; i < left; i++)
                {
                    hos.Add(hoseki[hosekiCount - 1 - i]);
                }

                var nokoriSosa = sosaCount - (right + left);
                hos.Sort();

                List<long> removed = new List<long>();
                var maxrem = new[] { nokoriSosa, hos.Count }.Min();

                for (int i = 0; i < maxrem; i++)
                {
                    if (hos[i] < 0)
                        removed.Add(hos[i]);
                    else break;
                }

                var sum = hos.Sum() - removed.Sum();
                if (sum > saidai)
                {
                    saidai = sum;
                }
            }
        }

        WriteLine(saidai);
        ReadKey();
    }
}


static class MyUtil
{
    public static int GetBit(this int num, int count)
    {
        int mask = (int)Math.Pow(2, count - 1);
        return (num & mask) == 0 ? 0 : 1;
    }

    public static int[] ToBit(this int num)
    {
        const int size = sizeof(int) * 8;
        var array = new int[size];
        for (int i = 0; i < size; i++)
        {
            array[i] = num.GetBit(size - i);
        }
        return array;
    }

    public static long[] ReadlongArray()
    {
        return ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray();
    }

    /// <summary>
    /// <see cref="IEnumerable{T}"/>の各要素を並べてコンソールに出力します。各要素の間には半角スペースが一つ入ります。
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="ts"></param>
    public static void WriteToConsole<T>(this IEnumerable<T> ts)
    {
        StringBuilder stringBuilder = new StringBuilder();
        foreach (T t in ts)
        {
            stringBuilder.Append(t.ToString());
            stringBuilder.Append(" ");
        }
        stringBuilder.Remove(stringBuilder.Length - 1, 1);
        Console.WriteLine(stringBuilder.ToString());
    }

    public static void WriteToDebugConsole<T>(this IEnumerable<T> ts)
    {
        StringBuilder stringBuilder = new StringBuilder();
        foreach (T t in ts)
        {
            stringBuilder.Append(t.ToString());
            stringBuilder.Append(" ");
        }
        stringBuilder.Remove(stringBuilder.Length - 1, 1);
        System.Diagnostics.Debug.WriteLine(stringBuilder.ToString());
    }
}


Measured memory_bytes: 13524
import java.lang.RuntimeException

fun main(args: Array<String>) {
    val line = readLine()!!.trim()
    val n = line.toInt()

    val hitoketa = n % 10
    val yomikata: String = if (listOf(2, 4, 5, 7, 9).contains(hitoketa)) {
        "hon"
    } else if (listOf(0, 1, 6, 8).contains(hitoketa)) {
        "pon"
    } else if (hitoketa == 3) {
        "bon"
    } else {
        throw RuntimeException("Oasii")
    }

    println(yomikata)
}

Measured memory_bytes: 38904
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()

using namespace std;

const ll M = 1e9+7;

void solve(int tc) {
    ll n;
    cin>>n;
    if(n==1) {
        cout<<0<<endl;
        return;
    } 
    ll total = 1;
    for(int i=0; i<n; ++i)
        total = (total*10)%M;
    ll x = 2;
    for(int i=0; i<n; ++i)
        x = (x*9)%M;
    ll y = 1;
    for(int i=0; i<n; ++i)
        y = (y*8)%M;
    cout<<(((total-x+y)%M)+M)%M<<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin>>t;
    for(int tc=1; tc<=t; ++tc) {
        solve(tc);
    }    
    return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define N 100005

using namespace std;
int n, m, u, v, d[N], F[N];
vector<int> A[N];

long long Magic(int a)
{
    if(A[a].size()==0) return 0;
    if(d[a]) return F[a];
    d[a]=1;
    long long res=0;
    for(int x: A[a])
    {
        res = max(res, Magic(x));
    }
    return F[a]=res+1;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>u>>v;
        A[u].push_back(v);
    }
    for(int i=1; i<=n; i++) A[0].push_back(i);
    cout<<Magic(0)-1;
    return 0;
}


Measured memory_bytes: 11956
# -*- coding: utf-8 -*-
"""
Created on Sun Aug  6 21:37:48 2017

@author: syaga
"""

if __name__ == "__main__":
    H, W = list(map(int, input().split()))
    N = int(input())
    a = list(map(int, input().split()))
    lis = [[None]*W for i in range(H)]
    ins = 1
    for i in range(H):
        for j in range(W):
            if a[0] == 0:
                del a[0]
                ins += 1
            lis[i][j] = ins
            a[0] -= 1
    for i in range(H//2):
        lis[2*i+1].reverse()
    for i in lis:
        print(" ".join(map(str, i)))


Measured memory_bytes: 3572
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;

int main(){
	char ch = ' ';

	while(1){
		scanf("%c",&ch);
		if( ch== '\n' ) break;
		
		if(islower(ch)){
			printf("%c",toupper(ch));
		}else if(isupper(ch)){
			printf("%c",tolower(ch));
		}else{
			printf("%c",ch);
		}
	}
	cout << "\n";
	return 0;
}

Measured memory_bytes: 1120
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
	int N;
	cin>>N;
	int A;
	int ans=0;
	for (int i=1;i<=N;i++){
		cin>>A;
		if (i%2==1 && A%2==1){
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

int main(){
  int a, b, c, x;
  cin >> a >> b >> c >> x;
  int ca = x / 500;
  if(ca > a){ca = a;}
  int i, j, k;
  int count = 0;
  for(i = 0; i <= ca; i++){
    int x1 = x - 500 * i;
    int cb = x1 / 100;
    if(cb > b){cb = b;}
    for(j = 0; j <= cb; j++){
      int x2 = x1 - 100 * j;
      if(x2 % 50 == 0 && x2/50 <= c){count++;}
    }
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

int get_GCD(u_int a, u_int b)
{
    while(a != 0 && b != 0){
        if(a >= b)
            a %= b;
        else
            b %= a;
    }
    return a != 0 ? a : b ;
}

int main()
{
    u_int a, b, GCD;
    while(std::cin >> a >> b){
            GCD = get_GCD(a, b);
            std::cout << GCD << " " << a * (b / GCD) << std::endl;
    }    

    return 0;
}

Measured memory_bytes: 1152
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int _i = 0; _i < (n); _i++) ni(a[_i])
#define nal(a, n) for (int _i = 0; _i < (n); _i++) nl(a[_i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 105;
const double eps = 1e-9;
char s[MAXN];
int dp[MAXN][2];

int main() {
	int n;
	scanf("%s", s);
	n = strlen(s);
	ll k; nl(k);
	int pre = 0, suf = n-1;
	for (; pre < n && s[0] == s[pre]; pre++);
	for (; suf >= 0 && s[n-1] == s[suf]; suf--);
	suf = n-suf-1;
	ll ans = pre / 2 + suf / 2;
	if (pre == n && suf == n)
		return !prl(((ll)n*k)/2);
	ll cnt = 0;
	for (int i = pre; i < n-suf; i++) {
		int j = i;
		for (; j < n && s[i] == s[j]; j++);
		cnt += (j-i) / 2;
		i = j-1;
	}
	if (s[0] != s[n-1]) {
		ans += cnt;
		prl(ans*k);
	} else {
		ans += k*cnt + (pre+suf)/2 * (k-1);
		prl(ans);
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/algorithm/string/classification.hpp> // is_any_of
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/math/tools/minima.hpp>

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

namespace adaptor = boost::adaptors;
using namespace std;
using boost::math::tools::brent_find_minima;
using boost::irange;
using boost::algorithm::join;
using boost::algorithm::split;
using boost::algorithm::replace_all;
using boost::multiprecision::cpp_int;
using ll = long long;
using P = pair<int, int>;

// TOP

void	Main()
{
	int	n;
	cin >> n;
	ll	power;
	power = 1;
	for (int i = 1; i <= n; i++)
	{
		power *= i;
		if (power >= 1000000007)
			power %= 1000000007;
	}
	cout << power << endl;
}
// END

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


Measured memory_bytes: 256
ans :: (Int,Int,Int) -> String
ans (a,b,c)
    | a*a + b*b == c*c = "YES"
    | a*a + c*c == b*b = "YES"
    | c*c + b*b == a*a = "YES"
    | otherwise        = "NO"

main = do
  c <- getContents
  let i = map (map read . words) $ tail $ lines c
      j = map (\(x0:x1:x2:xs) -> (x0,x1,x2)) i
      o = map ans j
  mapM_ (putStrLn) o

Measured memory_bytes: 4028
/* Simplicity and Goodness */
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

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

void my_dbg() { cout << endl; }
template<typename Arg, typename... Args> void my_dbg(Arg A, Args... B) 
{ cout << ' ' << A; my_dbg(B...); }
#define dbg(...)  cout << "(" << #__VA_ARGS__ << "):", my_dbg(__VA_ARGS__)

#define scn(n) scanf("%d", &n)
#define lscn(n) scanf("%lld", &n)
#define pri(n) printf("%d ", (int)(n))
#define prin(n) printf("%d\n", (int)(n))
#define lpri(n) printf("%lld ", n)
#define lprin(n) printf("%lld\n", n)
#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;

const int inf = INT_MAX;
const int ninf = INT_MIN;
const int mod = 1e9+7;
const int N = 2e5+2;


void solve()
{
    int n;
    scn(n);

    string s;
    cin >> s;

    map<int, int> fa;

    for(auto c : s)
        fa[c] ++;

    int ans = 1;

    for(auto x : fa) 
        ans = (1LL * ans * (1 + x.S)) % mod;

    ans = (ans - 1 + mod) % mod;

    prin(ans);
}

int main()
{
    int t = 1;
    // scn(t);

    while(t --) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 512
N, M = map(int, input().split())
links = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]
paths = 0

def search(cur, last):
    global paths
    if len(last) == 0:
        paths += 1
        return
    
    for i in list(last):
        if sorted([cur, i]) in links:
            pass_last = last.copy()
            pass_last.remove(i)
            search(i, pass_last)
    
search(0, set(range(1, N)))
print(paths)
            

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


#define fi first
#define se second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define el '\n'

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

const int N = 2e3 + 10;
const ll MOD = 1e9 + 7;

int n;
ll dp[2][N];
ll ans;

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

    cin >> n;
    for (int i=0;i<2;i++){
        fill(dp[i], dp[i] + N, 0);
    }
    dp[1][0] = 1;
    for (int i=0;i<n/3;i++){
        for (int j=0;j<n;j++){
            dp[0][j] = dp[1][j];
            if (j) dp[0][j] = (dp[0][j] + dp[0][j - 1]) % MOD;
            dp[1][j] = 0;
        }
        for (int j=3;j<=n;j++){
            dp[1][j] = dp[0][j - 3];
        }
        ans = (ans + dp[1][n]) % MOD;
    }
    cout << ans << el;

    return 0;
}

Measured memory_bytes: 3676
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        List<String> list = Arrays.asList("SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT");
        System.out.println(7 - list.indexOf(s));

        sc.close();
    }
}

Measured memory_bytes: 21972
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back

template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}

template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

//scanf("%lld", &);
//cin >> ;
//cout << ans << endl;

ll N, M, i, j, k, ans, cnt = 0;
string s;

int main(){
    //cin >> ;
    //cout << ans << endl;
    cin >> N;
    FOR(i, 1 , N){
        if(i % 3 != 0 && i % 5 != 0){
            ans += i;
        }
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

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

signed main(void)
{
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << max(a*b, c*d) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <numeric>
using namespace std;
typedef long long ll;

#define __ { \
	freopen("input.txt","r",stdin); \
	freopen("output.txt","w",stdout); \
}
#define _ { \
	ios_base::sync_with_stdio(false); \
    cin.tie(NULL); \
}

int main(){
   _;
  // __;
   string s;cin>>s;
   if(s=="AAA"||s=="BBB")cout<<"No";
   else cout<<"Yes";
}

Measured memory_bytes: 256
n = int(input())
Ad = [[] for _ in range(n)]
Deg = [0]*n
E = {}
E2 =[]
for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai-=1
    bi-=1
    Ad[ai].append(bi)
    Ad[bi].append(ai)
    Deg[ai] += 1
    Deg[bi] += 1
    E[(ai,bi)]=-1
    E[(bi,ai)]=-1
    E2.append((ai,bi))
mx = max(Deg)
print(mx)
E[(0,0)] = -1#後の都合
P =[-1]*n#parent
from collections import deque
Q = deque()
Q.append(0)
P[0] = 0

while Q:
    v = Q.popleft()
    for u in Ad[v]:
        if P[u]<0:
            P[u] = v
            Q.append(u)

Q = deque()
cnt = 1
for v in Ad[0]:
    E[(0,v)]=cnt
    E[(v,0)]=cnt
    cnt+=1
    Q.append(v)

while Q:
    v = Q.popleft()
    cnt = 1
    for u in Ad[v]:
        if E[(u,v)]<0:
            if cnt==E[(v,P[v])]:
                cnt +=1
            E[(u,v)] = cnt
            E[(v,u)] = cnt
            cnt+=1
            Q.append(u)
for i in range(n-1):
    print(E[E2[i]])
            



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

# In[6]:


A,B = map(int, input().split())


# In[8]:


ans = 0
for x in range(A,B+1):
    x = str(x)
    for i in range(len(x)//2):
        if x[i] != x[-(i+1)]:
            break
    else:
        ans += 1
print(ans)


# In[ ]:






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

struct node
{
    int l,r;
}p[100005];

int cmp(node x,node y)
{
    return x.r<y.r;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,L;
        scanf("%d %d",&x,&L);
        p[i].l=x-L;
        p[i].r=x+L;
    }
    sort(p+1,p+1+n,cmp);
    int poss=p[1].r;
    int ans=1;
    for(int i=2;i<=n;i++)
    {
        if(p[i].l>=poss)
        {
            ans++;
            poss=p[i].r;
        }
    }
    cout<<ans<<endl;
    return 0;

}


Measured memory_bytes: 1024
class UnionFindBySize():
    def __init__(self, n):
        self.parents = list(range(n+1))
        self.size = [1] * (n+1)

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    # 根が同一かどうかを判定する
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parents[x] = y
        else:
            self.size[x] += self.size[y]
            self.parents[y] = x

n, m = map(int, input().split())
AB = []
for _ in range(m):
    a, b = map(int, input().split())
    AB.append([a,b])

Ans = []
ans = 0
for i in range(1,n):
    ans += i
Ans.append(ans)

UF = UnionFindBySize(n)
for i in range(m):
    ab = AB[-1-i]
    a = ab[0]
    b = ab[1]
    if UF.same_check(a,b) == True:
        pass
    else:
        a_size = UF.size[UF.find(a)]
        b_size = UF.size[UF.find(b)]
        ans -= a_size*b_size
        UF.union(a,b)
    if i == m-1:
        break
    Ans.append(ans)

for i in range(m):
    print(Ans[-1-i])

Measured memory_bytes: 26376
# -*- coding: utf-8 -*-


def solve(m: int):
    from math import sqrt

    ans = dict()
    remain = m

    for j in range(2, int(sqrt(m)) + 1):
        if remain % j == 0:
            count = 0

            while remain % j == 0:
                count += 1
                remain //= j

            ans[j] = count

    if remain != 1:
        ans[remain] = 1

    return ans


def main():
    n = int(input())
    d = dict()
    mod = 10 ** 9 + 7
    ans = 1

    for i in range(2, n + 1):
        new = solve(i)

        for key, value in new.items():
            if key not in d.keys():
                d[key] = value
            else:
                d[key] += value

    for di in d.values():
        ans *= (di + 1)
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064