akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s,t;
    cin>>s>>t;
    int ls=s.length();
    int lt=t.length();
    int count=0;
    int temp=ls;
    for(int i=0;i<ls-lt+1;i++){
        int count=0;
        for(int j=0;j<lt;j++){
            if(s[i+j]!=t[j]) count+=1;
        }
        temp=min(temp,count);
    }
    cout<<temp<<endl;


        
}

Measured memory_bytes: 3624
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <math.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define ll long long
using namespace std;


int main(){
    const ll mod=1000000007;
    ll n;
    cin>>n;

    ll dp[n][2][2];

    dp[0][0][0]=8;
    dp[0][1][0]=1;
    dp[0][0][1]=1;
    dp[0][1][1]=0;

    for (int i=1;i<n;i++){
        for (int j=0;j<2;j++){
            for (int k=0;k<2;k++){
                if(j==0 && k==0) dp[i][j][k]=(dp[i-1][0][0]*8)%mod;
                if(j==1 && k==0) dp[i][j][k]=(dp[i-1][0][0]+(dp[i-1][1][0]*9)%mod)%mod;
                if(j==0 && k==1) dp[i][j][k]=(dp[i-1][0][0]+(dp[i-1][0][1]*9)%mod)%mod;
                if(j==1 && k==1) dp[i][j][k]=(dp[i-1][0][1]+dp[i-1][1][0]%mod+(dp[i-1][1][1]*10)%mod)%mod;
            }   
        }
    }
    cout<<dp[n-1][1][1]%mod<<endl;
    return 0;
}

Measured memory_bytes: 34784
class Vector:

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def move(self, offset):
        self.x += offset[0]
        self.y += offset[1]

    def move_offset(self, offset, multiple=1):
        x = self.x + offset[0] * multiple
        y = self.y + offset[1] * multiple
        return Vector(x, y)


class Pattern:
    NOTHING = " "
    EXIST = "#"
    SENTINEL = "?"

    MOVE = [
        [[-1, -1], [-1, +0], [-1, +1]],
        [[-1, +1], [-0, +1], [+1, +1]],
        [[+1, +1], [+1, +0], [+1, -1]],
        [[+1, -1], [+0, -1], [-1, -1]],
    ]

    @classmethod
    def create_area(cls, size):
        area = [[cls.SENTINEL] * 2 + [cls.NOTHING] * size + [cls.SENTINEL] * 2 for _ in range(size)]
        tmp = [[cls.SENTINEL] * size + [cls.SENTINEL] * 2 * 2]
        area = tmp * 2 + area + tmp * 2
        return area

    @classmethod
    def even_spiral_pattern(cls, area, point):
        move_index = 0
        area[point.x][point.y] = cls.EXIST

        while True:

            left, center, right = cls.MOVE[move_index]
            end1, end2 = point.move_offset(left), point.move_offset(right)
            offset, offset2 = point.move_offset(center), point.move_offset(center, 2)

            if area[end1.x][end1.y] == cls.EXIST or area[end2.x][end2.y] == cls.EXIST:
                return area
            elif area[offset.x][offset.y] == cls.NOTHING and area[offset2.x][offset2.y] != cls.EXIST:
                point.move(center)
                area[point.x][point.y] = cls.EXIST
            else:
                move_index += 1
                move_index %= 4

    @classmethod
    def odd_spiral_pattern(cls, area, point):
        move_index = 0
        is_end = False
        area[point.x][point.y] = cls.EXIST

        while True:

            left, center, right = cls.MOVE[move_index]
            offset, offset2 = point.move_offset(center), point.move_offset(center, 2)

            if area[offset.x][offset.y] == cls.NOTHING and area[offset2.x][offset2.y] != cls.EXIST:
                point.move(center)
                area[point.x][point.y] = cls.EXIST
                is_end = False
            else:
                if is_end:
                    return area
                else:
                    is_end = True

                move_index += 1
                move_index %= 4

    @classmethod
    def formater(cls, area):
        output = ["".join(item).replace(cls.SENTINEL, "") for item in area[2:-2]]
        output = "\n".join(output)
        return output

    @classmethod
    def solve(cls, size):
        area = cls.create_area(size)
        point = Vector(size - 1 + 2, 2)

        if size % 2 == 0:
            result = cls.even_spiral_pattern(area, point)
        else:
            result = cls.odd_spiral_pattern(area, point)

        return cls.formater(result)


sizes = [int(input()) for _ in range(int(input()))]
results = [Pattern.solve(num) for num in sizes]
print("\n\n".join(results))



Measured memory_bytes: 5752
#include "bits/stdc++.h"
 
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pl4 = pair<ll,ll>;
using str = string;
using vpl4 = vector<pair<ll,ll>>;

#define sz size()
#define be begin()
#define en end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define llin(x) ll (x);cin >>(x);
#define stin(x) str (x);cin >>(x);
#define FOR(i,a,b) for(ll i = a ; i <= b ; i++)
#define rFOR(i,b,a) for(ll i = a; i >= b ; i--)
#define SORT(x) sort(x.be, x.en)
#define rSORT(x) sort(x.rbegin(), x.rend())
#define say(x) cout<<(x);
#define sal(x) cout<<(x)<<endl;
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;
#define Imp(a) cout <<((a)?"Possible":"Impossible")<<endl;
#define IMP(a) cout <<((a)?"POSSIBLE":"IMPOSSIBLE")<<endl;

signed main(){
    vll n(4);
    ll a=0;
    ll b=0;
    ll c=0;
    ll d=0;
    FOR(i,0,3){
        cin >>n[i];
        if(n[i]==1) a=1;
        if(n[i]==9) b=1;
        if(n[i]==7) c=1;
        if(n[i]==4) d=1;
    }
    YN(a*b*c*d==1);
}


Measured memory_bytes: 256
# AOJ 2831: Check answers
# Python3 2018.7.12 bal4u

n = int(input())
if n == 0: print(0)
else:
	s = input()
	ans = 1
	for i in range(1, len(s)):
		if s[i-1] == 'x' and s[i] == 'x': break
		ans += 1
	print(ans)



Measured memory_bytes: 5788
function Main(input) {
	input = input.trim();
  var len = parseInt(input.split("\n")[0]);
  var list = input.split("\n")[1].split(" ").map((list)=>Number(list));
  var max = Math.max.apply(null,list);//最大値。
  var count = 0;
  var lastCount = 0;
  var mae = 0;
  for(var i = len - 1; i >= 0; i--){
    var tmp = list[i];
    //console.log(tmp);
    if(i == (len - 1)){
       //count++;
      mae = tmp;
       continue;
    }
    if(tmp < mae || i == 0){
      if(i == 0 && tmp >= mae){
         count++;
         }
       lastCount = Math.max(lastCount, count);
      count = 0;
    }else{
      count++;
    }
    mae = list[i];
  }
  console.log(lastCount);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 18696
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <valarray>
#include <utility>
#include <tuple>
#include <cmath>
#include <random>

using ll = long long;

//各種nil
template <class T>
constexpr T nil = static_cast<T>(-1);

constexpr int nil_i = nil<int>;
constexpr int nil_ll = nil<ll>;
constexpr double nil_d = nil<double>;

//vector
template <class T>
using vec = std::vector<T>;

struct Vec2D
{
    int x, y;
};

struct TimePos
{
    int time;
    Vec2D pos;
};

int ManhattanDistance(Vec2D v1, Vec2D v2)
{
    using namespace std;
    return abs(v1.x - v2.x) + abs(v1.y - v2.y);
}

void solve()
{
    using namespace std;
    string s;
    cin >> s;

    string out {};

    for (int i = 0; i < s.size(); ++i)
        if (i % 2 == 0)
            out.push_back(s[i]);

    cout << out << endl;
}

int main()
{
    solve();
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstdlib>
using namespace std;

int main() {
  
  string str; char op;
  while(cin>>str>>op) {
    if(op == 'X') break;
    for(int i=0; i<(int)str.size(); i++) {
      if(str[i] == '_') { str[i] = ' '; }
      else if(isupper(str[i])) {
        char ch = tolower(str[i]);
        str = str.substr(0, i) + " " + ch + str.substr(i+1);
      }
      else { str[i] = tolower(str[i]); }
    }
    stringstream ss(str);
    string ans;
    bool fsted = 0;
    while(ss >> str) {
      if(op == 'L') {
        if(fsted) { ans+=toupper(str[0]); ans+=str.substr(1); }
        else ans+=str;
        fsted = 1;
      }
      if(op == 'U') {
        ans+=toupper(str[0]); ans+=str.substr(1);
      }
      if(op == 'D') {
        if(fsted) ans+='_';
        ans+=str;
        fsted = 1;
      }
    }
    cout << ans << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1208
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
//#include <intrin.h>

#define fore(i,a,b) for(int i = a; i < (b); i++)
#define fr(i,a,b) for(int i = a - 1; i >= b; i--)
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define N 300005
#define inf 2000000000
#define EPS 1e-6
#define MOD 998244353ll
#define __builtin_popcount(x) __popcnt(x)

using namespace std;

typedef long long ll;

inline void solve()
{
	double a;
	cin >> a;
	cout << fixed << setprecision(10) << (a / 3) * (a / 3) * (a / 3);
}

int main()
{
	fast;
#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int q = 1;
	//cin >> q;
	while (q--)
	{
		solve();
		cout << '\n';
	}
}

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

#define M 1000000
#define L 14

char H[M][L]; /* Hash Table */

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){
  key = key%M;
  return key;
}
int h2(int key){
  key = 1+key%(M-1);
  return key;
}

int find(char str[]){

  long long sum,key2,i;

  sum = getKey(str);

  for(i=0; i<20; i++){

    key2 = (h1(sum)+i*h2(sum))%M;

    if(strcmp(H[key2],str)==0)return 1;
    if(strlen(H[key2])==0)return 0;
  }
}

int insert(char str[]){
  
  long long sum,key2,i;

  sum = getKey(str);

  for(i=0; i<20; i++){

    key2 = (h1(sum)+i*h2(sum))%M;

    if(strcmp(H[key2],str)==0)return 1;
    if(strlen(H[key2])==0){
      strcpy(H[key2],str);
      return 0;  
    }
  }
}

int main(){
    int i, n, h;
    char str[L], com[9];
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ){
	scanf("%s %s", com, str);
	
	if ( com[0] == 'i' ){
	    insert(str);
	} else {
	    if (find(str)){
		printf("yes\n");
	    } else {
		printf("no\n");
	    }
	}
    }

    return 0;
}

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

int main() {
  int h, w, k;
  cin >> h >> w >> k;
  vector<string> s(h);
  rep(i, h) cin >> s[i];
  int ans = 0;
  rep(is, 1<<h) rep(js, 1<<w) {
    int cnt = 0;
    rep(i, h)rep(j, w) {
      if (is>>i&1) continue;
      if (js>>j&1) continue;
      if (s[i][j] == '#') cnt++;
    }

    if (cnt == k) ans++;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3608
n, m, q = map(int, input().split())
query = []
for i in range(q):
	query.append(list(map(int, input().split())))

v = []
def dfs(u,ary):
	if len(ary) == n:
		ary.sort()
		cnt = 0
		for j in range(q):
			a,b,c,d = query[j]
			if ary[b-1] - ary[a-1] == c:
				cnt += d
		v.append(cnt)
	else:
		for j in range(u,m+1):
			dfs(j,ary+[j])


dfs(1,[1])

print (max(v))

Measured memory_bytes: 10828
a, b = map(int, input().split())
x = int(100 * a / 8)
y = int(100 * b / 10)
ans = min(x, y)
count = 0
ansi = 0
for i in range(30):
    ansi = ans + i
    if int(ansi * 8 / 100) == a and int(ansi * 10 / 100) == b:
        break
    count += 1
if count == 30:
    print("-1")
else:
    print(ansi)


Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<stack>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;


int main()
{
	int n;string str;
	cin >> n >> str;
	
	int now = 0,ans = 0;
	
	REP(i,n)
	{
		if(str[i] == 'I')
		{
			now++;
		}
		else
		{
			now--;
		}
		ans = max(ans,now);
	}
	
	cout << ans << endl;
	
	return 0;
}

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

//https://atcoder.jp/contests/dp/tasks

int main(){
    vector<vector<int>> dp;
    string s,t;
    cin >> s >> t;
    dp.assign(s.size()+1,vector<int>(t.size()+1,0));

    for(int i = 1;i <= s.size();i++){
        for(int j = 1;j <= t.size();j++){

            char chs = s[i-1];
            char cht = t[j-1];
            if(chs == cht){
                dp[i][j] = dp[i-1][j-1]+1;
            }

            if(dp[i][j]< dp[i-1][j]) dp[i][j] = dp[i-1][j]; 
            if(dp[i][j] < dp[i][j-1]) dp[i][j] = dp[i][j-1]; 

        }
    }


    string res = "";
    int i = (int)s.size(), j = (int)t.size();
    while (i > 0 && j > 0)
    {
        // (i-1, j) -> (i, j) と更新されていた場合
        if (dp[i][j] == dp[i-1][j]) {
            --i; // DP の遷移を遡る
        }

        // (i, j-1) -> (i, j) と更新されていた場合
        else if (dp[i][j] == dp[i][j-1]) {
            --j; // DP の遷移を遡る
        }

        // (i-1, j-1) -> (i, j) と更新されていた場合
        else {
            res = s[i-1] + res; // このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
            --i, --j; // DP の遷移を遡る
        }
    }
    cout << res << endl;


}

Measured memory_bytes: 38844
import java.io.*;

class Main {
	public static void main(String args[]) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(reader);
		
		//System.out.println("????????\???");
		String str = br.readLine();
		
		//System.out.println("??\?????????" +str);
		int mil = Integer.parseInt(str);
		
		int hour = mil / 3600;
		int minutes = (mil / 60) % 60;
		int seconds = mil % 60;
		
		System.out.println(hour + ":" + minutes + ":" + seconds);
	}
}

Measured memory_bytes: 24344
#include <cstdio>
#include <cmath>
#include <cstdint>
#include <cinttypes>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <map>

using namespace std;
static const long k10E7 = 1000000007;

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

    vector<string> sn(n);
    for(long i = 0; i < n ; i++){
        vector<char> in(11);
        cin >> &in[0];\
        sort(in.begin(), in.begin() + 10);
        
        sn[i] = &in[0];
    }

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

    long result = 0;

    long i = 0;
    long j = i + 1;

    while(j < n){
        if(sn[i] == sn[j]){
            result += (j - i);
            j++;
        } else {
            i = j;
            j = i + 1; 
        }
    }

    cout << result << endl;

    return 0;
}



Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)
#define RRep(i, k, n) for (int i = k; i > (int)(n); i--)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define ALL(a)  (a).begin(),(a).end()
#define rALL(a)  (a).rbegin(),(a).rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> void PrintVector(const vector<T> &vec) {for (auto val : vec) cout << val << " "; cout << endl;}
const long long INF = 1LL << 60;
const long long minusINF = -(1LL << 40);
const int MOD = 1000000007;
const double PI = acos(-1); //3.14~
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main()
{
    int n, t, a; cin >> n >> t >> a;
    vector<int> h(n);
    double mini = MOD;
    int ans = 0;
    rep(i, n)
    {
        cin >> h[i];
        double tmp = t - h[i] * 0.006;
        if (abs(tmp - a) < mini) ans = i + 1;
        mini = min(mini, abs(tmp - a));
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
//tokyokaijyo2020_b.cpp
//Sat Jul 11 10:15:25 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007
#define rep(i,n) for (int i=0;i<(n);++i)

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

int main(){
	ll a,v,b,w,t;
	cin >> a >> v >> b >> w >> t;

	if (w>=v){
		cout << "NO" << endl;
	}else if ((v-w)*t>=abs(b-a)){
		cout << "YES" << endl;
	}else {
		cout << "NO" << endl;
	}
}

Measured memory_bytes: 3648
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<cstdio>
#include<cstring>

using namespace std;

typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef string S;
typedef queue<int> qi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
struct edge{ ll to, cost; };//　一つ目は結んでいるノード,二つ目はその辺の重みを指す
//#define sort(a) sort(a.begin(),a.end())
using Graph = vector<vector<edge>>;  //隣接リスト
#define reverse(a) reverse(a.begin(),a.end())
#define pb push_back
#define elif else if
#define unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define mp make_pair
#define fr(i,n)for(ll i=0;i<(n);i++)
#define ifr(i,n)for(ll i=(n)-1;i>=0;i--)
#define ALL(a) (a).begin(),(a).end()
const int MOD = 1e9+7;
const ll INF =1e18;


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

Measured memory_bytes: 256
n = int(input())
li = []
ans_li = []
d = {}
for i in range(n):
    li.append(input())

for i in range(ord('a'),ord('z')+1):
    tmp = chr(i)
    d[tmp] = 10**5

for i in range(n):
    for j in range(ord('a'),ord('z')+1):
        tmp = chr(j)
        if li[i].count(tmp) < d[tmp]:
            d[tmp] = li[i].count(tmp)

for kk in d.keys():
    if d[kk] != 0:
        for i in range(d[kk]):
            ans_li.append(kk)

print("".join(sorted(ans_li)))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=(ll)(1e9+7);
ll run();

int main() {
#ifdef home
    freopen("i", "r", stdin);
    freopen("d", "w", stderr);
#endif
    cout.precision(15);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    run();
    return 0;
}
const ll inf = (1e9+5);
void max_self(ll &a, ll b) {
    a = max(a, b);
}
void min_self(ll &a, ll b) {
    a = min(a, b);
}
void mul(ll &a, ll b) {
    a = (a * b) % mod;
}
void add_self(ll &a, ll b){
    a+=b;
    if(a>=mod)
        a-=mod;
}
ll gcd(ll a, ll b){
    return b?gcd(b,a%b):a;
}

vector<ll> a(405);
vector<ll> ps(405);
ll dp[405][405];

ll solve(int i, int j){
    if(i==j)
        return 0;
    if(dp[i][j]!=-1)
        return dp[i][j];
    ll s = ps[j]-ps[i-1];
    ll ans = LLONG_MAX;
    for(int k=i;k<j;k++){
        ans = min(ans,solve(i,k)+solve(k+1,j)+s);
    }
    return dp[i][j] = ans;
}

ll run() {
    int n;
    cin>>n;
    memset(dp,-1,sizeof(dp));
    ll s = 0;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        s+=a[i];
        ps[i] = s;
    }

    ll ans = solve(1,n);
    cout<<ans;
    return 0;
}















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

int main()
{
    string s;
    char ch;
    int hast;

    cin >> s;

    for(ch='a'; ch<='z'; ch++)
    {
        hast=0;

        for(int i=0; i<s.size(); i++)
        {

            if(ch==s[i])
                hast=1;
        }


        if(hast==0)
        {
            cout<<ch;
            break;
        }


    }
    if(hast==1)
    {
        cout << "None";
    }
    return 0;
}


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

using namespace std;

using ll = long long;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORE(i, a, b) for (int i = (a); i <= (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define all(v) (v).begin(), (v).end()
#define sp cout << fixed << setprecision(10)
typedef pair<int, int> P;
const int inf = (int)1e9;
const int mod = (int)1e9 + 7;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

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

    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;

    int cumsum[n + 1] = {};
    cumsum[0] = 0;
    int cnt = 0;
    bool a = false;
    rep(i, n) {
        cumsum[i + 1] = cumsum[i];
        if (a and s[i] == 'C') {
            cnt++;
            cumsum[i + 1] = cnt;
            a = false;
        } else if (s[i] == 'A') {
            a = true;
        } else {
            a = false;
        }
    }
    // rep(i, n + 1) cout << cumsum[i] << " ";

    rep(i, q) {
        int l, r;
        cin >> l >> r;
        cout << cumsum[r] - cumsum[l] << endl;
    }

    return 0;
}


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

int main() {
  string s;
  cin >> s;
  vector<int> a(4);
  rep(i, 4) a.at(i) = (char)s.at(i) - '0';

  for (int i = 0; i < (1 << 4); i++) {
    bitset<4> b(i);
    int sum = a.at(0);
    rep(j, 3) sum += a.at(j + 1) * (b.test(j) ? 1 : -1);

    if (sum == 7) {
      cout << a.at(0);
      rep(j, 3) cout << (b.test(j) ? "+" : "-") << a.at(j + 1);
      cout << "=7" << endl;
      break;
    }
  }
  return 0;
}


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

const int MAX_V = 525;

long long N, A[22];
long long dp[22][22][601][601];

void solve(int cl, int cr) {
	if (cr - cl == 1) {
		for (int i = 1; i <= MAX_V; i++) {
			for (int j = 1; j <= MAX_V; j++) {
				dp[cl][cr][i][j] = 0;
			}
		}
		return;
	}
	for (int i = 1; i <= MAX_V; i++) {
		for (int j = 1; j <= MAX_V; j++) {
			dp[cl][cr][i][j] = (1LL << 61);
			for (int k = cl + 1; k <= cr - 1; k++) {
				long long p1 = 0LL;
				if (k - cl == 2) p1 = 1LL * (i + (i + j)) * A[cl + 1];
				if (k - cl == 3) {
					int a = i, b = i + j;
					p1 = min(1LL * (a + b) * A[cl + 1] + 1LL * (a + b + b) * A[cl + 2], 1LL * (a + b) * A[cl + 2] + 1LL * (a + a + b) * A[cl + 1]);
				}
				if (k - cl >= 4) { if (i + j > MAX_V) continue; p1 = dp[cl][k][i][i + j]; }

				long long p2 = 0LL;
				if (cr - k == 2) p2 = 1LL * (j + (i + j)) * A[cr - 1];
				if (cr - k == 3) {
					int a = i + j, b = j;
					p2 = min(1LL * (a + b) * A[cr - 2] + 1LL * (a + b + b) * A[cr - 1], 1LL * (a + b) * A[cr - 1] + 1LL * (a + a + b) * A[cr - 2]);
				}
				if (cr - k >= 4) { if (i + j > MAX_V) continue; p2 = dp[k][cr][i + j][j]; }

				dp[cl][cr][i][j] = min(dp[cl][cr][i][j], p1 + p2 + 1LL * (i + j) * A[k]);
			}
		}
	}
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];

	for (int i = 1; i < N; i++) {
		for (int j = 1; j <= N - i; j++) {
			solve(j, j + i);
		}
	}
	cout << dp[1][N][1][1] + 1LL * A[1] + 1LL * A[N] << endl;
	return 0;
}

Measured memory_bytes: 461184
#exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'},'/usr/bin/ruby', $0) if !ENV['RUBY_THREAD_VM_STACK_SIZE']
require 'prime'

def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

def sum(a) a.inject(:+) end

def big(a,b) return (a>b)? a:b end

def small(a,b) return (a<b)? a:b end
  
a = inp
t = 0
t += (a[2] - a[0])*60
t += (a[3] - a[1])
p t - a[4] 

Measured memory_bytes: 14452
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
using vll=vector<ll>;
using vvll=vector<vll>;


int main(void)
{
	int r;

	while(scanf("%d", &r)==1)
	{
		int ans=3*r*r;

		printf("%d\n", ans);
	}
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>

int main(){
  std::string S;
  std::cin >> S;
  int first = int(S[1])-int('0') + 10*(int(S[0])-int('0'));
  int second = int(S[3])-int('0') + 10*(int(S[2])-int('0'));
  bool first_month = false;
  bool second_month = false;
  if (first>=1 && first<=12){
    first_month=true;
  }
  if (second>=1 && second<=12){
    second_month=true;
  }
  if(first_month && second_month){
    printf("AMBIGUOUS\n");
  } else if (first_month){
    printf("MMYY\n");
  } else if (second_month){
    printf("YYMM\n");
  } else {
    printf("NA\n");
  }
  return 0;
}


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

#満足度D
d = [0 for k in range(n)]
d[0]=b[a[0]-1]

for i in range(1, n):
    if a[i]==a[i-1]+1:
        d[i]=b[a[i]-1]+c[a[i-1]-1]
    else:
        d[i]=b[a[i]-1]
        
ans = 0
for j in range(n):
    ans += d[j]

print(ans)

Measured memory_bytes: 3064
import numpy as np

n = int(input())

"""
directly out
*ag c
indirectly

*ga c
*ac g
a*g c
ag* c

a =0
c =1
g = 2
t = 3
"""

l = ["a","g","c","t"]
bef = {"a":1,"g":1,"c":1,"t":1}
d = {}
m = {}

for i in range(4):
    for j in range(4):
        for k in range(4):
            temp = l[i]+l[j]+l[k]
            d[temp] = 1
d["agc"] = 0
d["acg"] = 0
d["gac"] = 0





for key in d.keys():
    if key[1:] == "ag":
        m[key] = {key[1:]+"a":1,key[1:]+"g":1,key[1:]+"c":0,key[1:]+"t":1}
    elif key[1:] == "ga":
        m[key] = {key[1:] + "a": 1, key[1:] + "g": 1, key[1:] + "c": 0, key[1:] + "t": 1}
    elif key[1:] == "ac":
        m[key] = {key[1:] + "a": 1, key[1:] + "g": 0, key[1:] + "c": 1, key[1:] + "t": 1}
    elif key[0] == "a" and key[2] == "g":
        m[key] = {key[1:] + "a": 1, key[1:] + "g": 1, key[1:] + "c": 0, key[1:] + "t": 1}
    elif key[0] == "a" and key[1] == "g":
        m[key] = {key[1:] + "a": 1, key[1:] + "g": 1, key[1:] + "c": 0, key[1:] + "t": 1}
    else:
        m[key] = {key[1:] + "a": 1, key[1:] + "g": 1, key[1:] + "c": 1, key[1:] + "t": 1}

mod = 10**9 +7
for i in range(n-3):
    buf = {}
    for i in range(4):
        for j in range(4):
            for k in range(4):
                temp = l[i] + l[j] + l[k]
                buf[temp] = 0
    for key in d.keys():
        for to in m[key].keys():
            buf[to] += d[key]*m[key][to]
            buf[to] = buf[to]%mod
    d = buf

ans = 0
for key in d.keys():
    ans += d[key]
print(ans%mod)






Measured memory_bytes: 12512
#define _USE_MATH_DEFINES

#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <set>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
#include <regex>
#include <cmath>
#include <map>
#include <iterator>
#include <climits>
#include <numeric>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <array>
#include <valarray>
#include <complex>
#include <random>
#include <functional>
#include <cassert>
#include <chrono>
#include <memory>

using namespace std;

#define int long long
//region TEMPLATE
#define double long double
typedef long long ll;
typedef unsigned long long ull;

template<typename T>
void __read(T &a) { cin >> a; }

template<typename T, typename ... Args>
void __read(T &a, Args &... args) {
    cin >> a;
    __read(args...);
}

#define make(t, ...) t __VA_ARGS__; __read(__VA_ARGS__)
#define makev(a, n) VI a(n); FOR(n) cin >> a[i];
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define FORIT(p) for(auto it = p.begin(); it != p.end(); it++)
#define FOR(b) for(signed i = 0; i <(b); i++)
#define FORE(i, l, r) for(int i = (l); i < (r); i++)
#define NFOR(i, n) for(int i = (((int) n)-1); i >= 0; i--)
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef pair<pair<int, int>, int> PPII;
constexpr ll M7 = 1000000007ll;
constexpr ll M9 = 1000000009ll;
constexpr ll MFFT = 998244353ll;
template<class T>
void outv(T &a) { for (auto &x : a) cout << x << ' '; }
static mt19937 rnd(static_cast<unsigned>(chrono::steady_clock::now().time_since_epoch().count())); // NOLINT(cert-err58-cpp)
template<class T>
static auto __super_speed__ = (ios_base::sync_with_stdio(0), cin.tie(
        0)); // NOLINT(cert-err58-cpp,cppcoreguidelines-interfaces-global-init)
//endregion

int32_t main() {
    make(int, n);
    makev(a, n);
    sort(ALL(a));
    int d = (1 + M7) / 4, res = 0;
    for(int i = 0; i < n; ++i){
        res += a[i] * (n - i + 1) % M7;
        d = d * 4 % M7;
    }
    cout << res % M7 * d % M7;
    return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#define N 101
#define NIL -1
#define INF 10000

int G[N][N];
int n;

int prim(int r) {
	int i,u,ans=0;
	int d[N];
	int pi[N];
	int mincost;
	char color[N];

	for(i=1;i<=n;i++){
		d[i] = INF;
		pi[i] = NIL;
		color[i] = 'W';
	}

	d[r] = 0;

	while(1) {
		mincost = INF;
		for (i=1;i<=n;i++) {
			if (color[i] != 'B' && d[i] < mincost) {
				mincost = d[i];
				u = i;
			}
		}

			if (mincost == INF) break;

			color[u] = 'B';

			for (i=1;i<=n;i++) {
				if (G[u][i] != NIL) {
					if(color[i] != 'B' && G[u][i] < d[i]) {
						pi[i] = u;
						d[i] = G[u][i];
					}
				}
			}
	}
	for (i=1;i<=n;i++) {
		ans += d[i];
	}
	return ans;
}

int main() {
	int i,j;
	int ans;

	scanf("%d", &n);

	for(i=1;i<=n;i++) {
		for(j=1;j<=n;j++) {
			scanf("%d", &G[i][j]);
		}
	}

	ans = prim(1);

	printf("%d\n", ans);

	return 0;
}

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

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

    for(int j=0; j<N-1; j++){
        for(int k=j; k<N; k++){
            if(X[j]>X[k]){
                int tmp=X[j];
                X[j]=X[k];
                X[k]=tmp;
            }
        }
    }

    int deltaX = X[N-1]-X[0];

    if(deltaX==0){
        cout<< 0 << "\n";
    }else{
    int sum_work_P[deltaX];
    int each_work_P;

    for(int i=0; i<deltaX; i++){
        int P = X[0]+i;
        sum_work_P[i]=0;
        for(int j=0; j<N; j++){
            each_work_P = (X[j]-P)*(X[j]-P);
            sum_work_P[i]+=each_work_P;
        }
    }

    for(int i=0; i<deltaX-1; i++){
        for(int j=i; j<deltaX; j++){
            if(sum_work_P[i]>sum_work_P[j]){
                int tmp=sum_work_P[j];
                sum_work_P[j]=sum_work_P[i];
                sum_work_P[i]=tmp;
            }
        }
    }

    cout << sum_work_P[0] << "\n";
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int a, b, c, x, y;
    int sum = 0;
    scanf("%d %d %d %d %d", &a, &b, &c, &x, &y);
    if ((a + b) > c * 2) {
        if (x >= y) {
            sum = sum + y * c * 2;
        } else {
            sum = sum + x * c * 2;
        }
    }  else {
        if (x >= y) {
            sum = sum + y * (a + b);
        } else {
            sum = sum + x * (a + b);
        }
    }
    if (x >= y) {
        if (a > 2 * c)
            sum = sum + (x - y) * 2 * c;
        else
            sum = sum + (x - y) * a;
    } else {
        if (b > 2 * c)
            sum = sum + (y - x) * 2 * c;
        else
            sum = sum + (y - x) * b;
    }
    printf("%d\n", sum);
    return 0;
}

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

typedef long long ll;

const int maxn = 1e5 + 5;

int main(int argc, const char * argv[])
{
    ll n, h[maxn], dp[maxn];
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &h[i]);
    
    dp[0] = 0; dp[1] = h[0]; dp[2] = abs(h[2] - h[1]);
    for (int i = 3; i <= n; i++)
        dp[i] = min(dp[i-2] + abs(h[i] - h[i-2]), dp[i-1] + abs(h[i] - h[i-1]));

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

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

typedef long long ll;
int N;
ll a[100005];
ll b[100005];

ll solve(){
  ll res=0,sum=0;
  for(int i=0;i<N;i++){
    sum+=a[i];
    if(i%2==0){
      if(sum<=0){
        res+=abs(sum)+1;
        sum=1;
      }
    }else{
      if(sum>=0){
        res+=abs(sum)+1;
        sum=-1;
      }
    }
  }
  return res;
}

ll solve2(){
  ll res=0,sum=0;
  for(int i=0;i<N;i++){
    sum+=a[i];
    if(i%2==1){
      if(sum<=0){
        res+=abs(sum)+1;
        sum=1;
      }
    }else{
      if(sum>=0){
        res+=abs(sum)+1;
        sum=-1;
      }
    }
  }
  return res;
}

int main(){
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>a[i];
  }
  cout<< min(solve(),solve2())<<endl;
  return 0;
}


Measured memory_bytes: 1152
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
string s;
  cin >>s;
  int x=s.size();
  if(x%2 !=0) {
    
    rep(i,x/2+1) {
      cout<<s.at(2*i);
    }
  }

else {
  rep(i,x/2) {
    cout<<s.at(2*i);
  }
}





}
 

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define RALL(a)     (a).rbegin(),(a).rend()
#define PRINT(a)   cout << (a) << endl

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second

#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

using ll = long long int;
using P = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

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

const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;
const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};


mint mpow(int x, int n){
  if(n==0)return 1;

  mint y = mpow(x, n/2);
  y *= y;

  if(n%2==1) y *=x;
  return y;
}

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};


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

  vector<P> lr;
  REP(i,k){
    int l,r;
    cin >> l >> r;
    lr.emplace_back(l,r);
  }

  vector<mint> sum(n+1,0);
  sum[1]=1;

  FOR(i,2,n+1){
    sum[i] = sum[i-1];
    mint tmp=0;
    for(auto v: lr){
      int l = i - v.second;
      int r = i - v.first;
      if(r < 1){
        continue;
      }else if(l >= 1){
        tmp += sum[r] - sum[l-1];
      }else{
        tmp += sum[r];
      }
    }
    sum[i] += tmp;

  }
  // REP(i,n+1){
  //   cout << i << " " << sum[i].x << endl;
  // }
  cout << (sum[n] - sum[n-1]).x << endl;
}



Measured memory_bytes: 4840
#include <stdio.h>

int main(){
   int a,b,c;
    
   scanf("%d %d",&a,&b);
   if ((a+b)>a*b) c=a+b;
   else           c=a*b;
   if (c<a-b) c=a-b;
   printf("%d\n",c);
   return 0;
}


Measured memory_bytes: 128
object Main extends App {
  val ans = scala.io.StdIn.readLine().split(" ").toList.map(_.toInt) match {
    case List(a: Int, b: Int) if a == b => "a == b"
    case List(a: Int, b: Int) if a < b => "a < b"
    case _ => "a > b"
  }
  println(ans)
}

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

int main ( ) {

    int N;
    string S;
    cin >> N;
    for (int i=0;  i<N; i++) {
        cin >> S;

        if (S=="Y") {
            cout << "Four" << endl;
            break;
        }
        else if (i==N-1) {
            cout << "Three" << endl;    
        }
    }
}  


Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
#define YN(a) if(a){cout<<"Yes"<<endl;}else cout<<"No"<<endl;//条件によってYes、Noを出力する
int main(){
    int n,W;
    cin>>n>>W;
    //int sum=0;
    vector<int64_t> w(n),v(n);
    rep(i,n){
        cin>>w[i]>>v[i];
    }
    //int64_t dp[101][100001]={};
    vector<vector<int64_t>> dp(n+1,vector<int64_t> (W+1,0));
    //dp[i][j]=i-1個目までの品物を重さjを超えないように選んだ時の価値の最大値,dp[n][w]が答え
    /*
    rep(i,W+1){
        dp[0][i] = 0;
    }
    rep(i,n+1){
        dp[i][0] = 0;
    }
    */
    rep(i,n){
        rep(j,W+1){
            if(j-w[i]<0){
                dp[i+1][j] = dp[i][j];
            }
            else{
                dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]);
            }
        }
    }
    /*
    rep(i,n+1){
        rep(j,W+1){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    cout<<dp[n][W]<<endl;
}

Measured memory_bytes: 80256
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
    
int main(){
    u_int n;    // the number of vegetable
    u_int m;    // capacity
       
    while(std::cin >> n >> m){
        if(n == 0 && m == 0){
            break;
        }
            
        std::vector<u_int> p(n);  // price
        for(int i = 0; i < n; ++i){
            std::cin >> p[i];
        }
           
        //m, 2*m, 3*m, ... = free(sort by descending)
        std::sort(p.begin(), p.end(), std::greater<u_int>());
        for(int i = m; i <= n; i += m){
            p[i-1] = 0;
        }
           
        std::cout << std::accumulate(p.begin(), p.end(), 0) << std::endl;
    }
        
    return 0;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
int main(){
  int64_t a = 2;
  int64_t b = 1;
  int N;
  cin >> N;
  int i=0;
  while (i<N-1){
    if(i%2 == 0){
      a = a+b;
      i++;
    }
    else {
      b = a+b;
      i++;
    }
  }
  if (i%2 == 0){
    cout << b << endl;
  } else {
    cout << a << endl;
  }
}

Measured memory_bytes: 256
N = int(input())
L = [0]*N
L[0] = list(map(int, input().split()))
for i in range (1,N):
  L[i] = list(map(int, input().split()))
  L[i][0] += max(L[i-1][1], L[i-1][2])
  L[i][1] += max(L[i-1][0], L[i-1][2])
  L[i][2] += max(L[i-1][0], L[i-1][1])
print(max(L[N-1]))

Measured memory_bytes: 30180
#include <iostream>

#include <complex>
#include <vector>
#include <cmath>

const double EPS=1e-10;

#define equals(a, b) (fabs((a)-b(b))<EPS)
#define X real()
#define Y imag()

using namespace std;

typedef complex<double> Point;
typedef complex<double> Vector;

struct Segment {
    Point p1, p2;
};
typedef Segment Line;

struct Circle {
    Point c;
    double r;
    Circle(Point c=Point(), double r=0.0) :
        c(c),r(r){}
};

typedef vector<Point> Polygon;

double dot(Vector a, Vector b) {
    return a.X*b.X + a.Y*b.Y;
}

double cross(Vector a,Vector b) {
    return a.X*b.Y - a.Y*b.X;
}

Point project(Segment s, Point p) {
    Vector base = s.p2-s.p1;
    double r=dot(p-s.p1,base) / norm(base);
    return s.p1+base*r;
}

Point reflect(Segment s, Point p) {
    return p+(project(s,p)-p)*2.0;
}

enum CCW {
    COUNTER_CLOCKWISE=1,
    CLOCKWISE=-1,
    ONLINE_BACK=2,
    ONLINE_FRONT=-2,
    ON_SEGMENT=0,
};

int ccw(Point p0, Point p1, Point p2) {
    Vector a=p1-p0;
    Vector b=p2-p0;
    if(cross(a,b)>EPS) return CCW::COUNTER_CLOCKWISE;
    if(cross(a,b)<-EPS) return CCW::CLOCKWISE;
    if(dot(a,b)<-EPS) return CCW::ONLINE_BACK;
    if(norm(a)<norm(b)) return CCW::ONLINE_FRONT;

    return CCW::ON_SEGMENT;
}

bool intersect(Point p1,Point p2,Point p3,Point p4) {
    return (ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0&&
            ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0);
}
bool intersect(Segment s1,Segment s2) {
    return intersect(s1.p1,s1.p2,s2.p1,s2.p2);
}

int main() {
    int q;
    cin>>q;
    while(q-->0) {
        double x1,y1;
        double x2,y2;
        double x3,y3;
        double x4,y4;
        cin>>x1>>y1;
        cin>>x2>>y2;
        cin>>x3>>y3;
        cin>>x4>>y4;
        Segment s1=Segment({Point(x1,y1),Point(x2,y2)});
        Segment s2=Segment({Point(x3,y3),Point(x4,y4)});
        if(intersect(s1,s2)) {
            cout<<"1"<<endl;
        }
        else cout<<"0"<<endl;
    }

    return 0;
}

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

int main() {
  int a,b;
  cin>>a>>b;
  if(a>=b){
    for(int i=0;i<a;i++){
      cout<<b;
    }
    cout<<endl;
  }
  else{
    for(int i=0;i<b;i++){
      cout<<a;
    }
    cout<<endl;
  }
}

  


Measured memory_bytes: 256
# include <iostream>
# include <stdio.h>
using namespace std;
int main(){
    char ch;
    while(1){
    scanf("%c", &ch);
    if('a' <= ch && ch <= 'z'){
        printf("%c",ch - 32);
    }else if('A' <= ch && ch <= 'Z'){
        printf("%c",ch + 32);
    }else{
      printf("%c",ch);
    }

    if ( ch == '\n' ) break;
}
}



Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,wt;
    cin>>n>>wt;
    long long w[n],val[n];
    long long sum=0;
    for(int i=0;i<n;i++){
        cin>>w[i]>>val[i];
        sum+=val[i];
    }
    long long dp[2][sum+1];
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<sum+1;j++){
            dp[i][j]=INT_MAX;
        }
    }
    dp[0][0]=0;
    for(long long i=1;i<n+1;i++){
        for(long long j=0;j<sum+1;j++){
            if(val[i-1]<=j){
                dp[1][j]=min(dp[0][j],w[i-1]+dp[0][j-val[i-1]]);
            }
            else
                dp[1][j]=dp[0][j];
        }
        for(int k=0;k<sum+1;k++){
            //cout<<setw(10)<<dp[1][k]<<" ";
            dp[0][k]=dp[1][k];
            dp[1][k]=INT_MAX;
        }
    }
    long long ans=INT_MIN;
    for(long long i=0;i<=sum;i++){
        if(dp[0][i]<=wt)
            ans=max(ans,i);

    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(),v.end()
#define repf(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
#define MOD 998244353 

using namespace std;
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<ll> ors;

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

ll power(ll a, ll n, ll m)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans=(ans*a)%m;
        n>>=1;
        a=(a*a)%m;
    }
    return ans;
}

ll invmod(ll a, ll m)
{
    return power(a,m-2,m);
}

ll lp[10000001];

void prime()
{
    repf(i,1,10000001) lp[i]=i;
    repf(i,2,10000001)
    {
        if(lp[i]==i)
        {
            for(ll j=2*i;j<10000001;j+=i)
            {
                if(lp[j]==j) lp[j]=i;
            }
        }
    }
}

ll w(ll a, ll b) {
    ll res=(b/2)*(a/2)+ceil((ld)b/2)*ceil((ld)a/2);
    return res;
}

ll W(ll a, ll b, ll c, ll d) {
    return w(c,d)-w(a-1,d)-w(c,b-1)+w(a-1,b-1);
}

ll B(ll a, ll b, ll c, ll d) {
    return (c-a+1)*(d-b+1)-W(a,b,c,d);
}

void solve(ll tt) {
    ll n;
    cin>>n;
    ll len=1,s=26;
    while(n>s) {
        n-=s;
        s*=26;
        len++;
    }    
    n--;
    string ans;
    ans.resize(len);
    repb(i,len-1,0) {
        ans[i]=n%26+'a';
        n/=26;
    }
    cout<<ans<<endl;
}

int main()
{
    IOS;
    ll t;
    // cin>>t;
    t=1;
    repf(tt,1,t+1) {
        solve(tt);
    }
}     

Measured memory_bytes: 3660