akhauriyash/Code-Regression huggingface dataset:
#include <set>
#include <cstdio>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#define mp make_pair

using namespace std;

int h, w, s;
int u[32][32];
int sm[33][33][33][33];
int all;
pair<int, int> memo[33][33][33][33];

int calcs(int x1, int y1, int x2, int y2){
  if(sm[x1][y1][x2][y2]) return sm[x1][y1][x2][y2];
  if(x1 + 1 == x2 && y1 + 1 == y2)
    return sm[x1][y1][x2][y2] = u[y1][x1];

  int ret;
  if(y1 + 1 == y2){
    ret = calcs(x1, y1, x2 - 1, y2) + calcs(x2 - 1, y1, x2, y2);
  }else{
    ret = calcs(x1, y1, x2, y2 - 1) + calcs(x1, y2 - 1, x2, y2);
  }
  return sm[x1][y1][x2][y2] = ret;
}

int main(){
  while(scanf("%d%d%d", &h, &w, &s), h + w + s){
    REP(i,h) REP(j,w) scanf("%d", &u[i][j]);
    REP(i,h) REP(j,w)
      for(int k = i; k < h; k++)
	for(int l = j; l < w; l++)
	  sm[j][i][l+1][k+1] = 0;

    REP(i,h) REP(j,w)
      for(int k = i; k < h; k++)
	for(int l = j; l < w; l++){
	  calcs(j, i, l + 1, k + 1);
	  memo[j][i][l+1][k+1].first = -1;
	}
    all = sm[0][0][w][h];

    for(int ww = 1; ww <= w; ww++){
      for(int hh = 1; hh <= h; hh++){
	for(int xx = 0; xx + ww <= w; xx++){
	  for(int yy = 0; yy + hh <= h; yy++){
	    int sum = sm[xx][yy][xx + ww][yy + hh];
	    int tmp = all - sum;
	    pair<int, int> ret(-1, -1);

	    if(tmp <= s) ret = mp(1, s - tmp);

	    for(int www = 1; www < ww; www++){
	      pair<int, int> r1 = memo[xx][yy][xx + www][yy + hh];
	      pair<int, int> r2 = memo[xx + www][yy][xx + ww][yy + hh];

	      if(r1.first == -1 || r2.first == -1) continue;

	      pair<int, int> r3 = mp(r1.first + r2.first, min(r1.second, r2.second));
	      ret = max(ret, r3);
	    }
	    for(int hhh = 1; hhh < hh; hhh++){
	      pair<int, int> r1 = memo[xx][yy][xx + ww][yy + hhh];
	      pair<int, int> r2 = memo[xx][yy + hhh][xx + ww][yy + hh];
	      
	      if(r1.first == -1 || r2.first == -1) continue;
	      
	      pair<int, int> r3 = mp(r1.first + r2.first, min(r1.second, r2.second));
	      ret = max(ret, r3);
	    }

	    memo[xx][yy][xx + ww][yy + hh] = ret;
	  }
	}
      }
    }
    
    pair<int, int> ret = memo[0][0][w][h];
    
    printf("%d %d\n", ret.first, ret.second);
  }

  return 0;
}

Measured memory_bytes: 14000
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iomanip>

using namespace std;

int main()
{
  int N, Q;
  string S;
  cin >> N >> Q >> S;

  vector<int> l(Q), r(Q);
  for (int i = 0; i < Q; ++i) cin >> l[i] >> r[i];

  int count = 0;
  vector<int> c((int)S.size());
  for (int i = 1; i < N; ++i)
  {
    if (S[i - 1] == 'A' && S[i] == 'C') ++count;
    c[i] = count;
  }

  for (int i = 0; i < Q; ++i)
  {
    cout << c[r[i] - 1] - c[l[i] - 1] << endl;
  }
}


Measured memory_bytes: 2176
#include<bits/stdc++.h>
    #define sz(a) (int)(a).size()
    #define debug(x) (cerr << #x << ": " << x << "\n")
     
    using namespace std;
     
    template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
    template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
    const int INF = 1e5+2;
    const long long hell = 998244353ll;
     
    int n , m , ans = 0;
    vector<int>color(INF,2);
    vector<vector<int>>bp(2);
    vector<vector<char>>arrr(INF);
    char arr[51][51];
    vector<vector<bool>>bani(51,vector<bool>(51,false));
     
    void dfs(pair<int,int>v , pair<int,int> p , pair<int,int> pp , int k){
    	if(bani[v.first][v.second] || ans ) return;
    	bani[v.first][v.second] = true;
    	if(k >= 4 && p != pp && v != p){
    	 	ans = 1;
    	 	return;
	}
	
    }
     
    void solve(){
    	cin >> n >> m;
    	int cnt = 0;
    	vector<int>arr(n); 
    	for(int i = 0 ; i < n ; i++ ){ 
    		cin >> arr[i];
    		if(arr[i]>=m) cnt++;
    	}
    	cout<< cnt <<endl; 	
    	
    		
    }
    int main(){
        	
    	ios_base::sync_with_stdio(0);cin.tie(0);
    	  cout.precision(10);
    cout << fixed;	
    	int q=1;
    #ifdef LOCAL
      	cin>>q;
    #endif
      	while(q--){
      		solve();
      	}
    #ifdef LOCAL
       	cout << "Time elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif	
    	return 0;
    }

Measured memory_bytes: 3456
#include <stdio.h>
#include <math.h>

int
main(void)
{
	char line[80];
	int n;

	if (fgets(line, sizeof line, stdin) == NULL) {
		return 1;
	}
	if (sscanf(line, "%d", &n) != 1) {
		return 1;
	}

	double x1;
	double x2;
	double x3;
	double y1;
	double y2;
	double y3;

	for (int i = 0; i < n; i++) {
		if (fgets(line, sizeof line, stdin) == NULL) {
			return 1;
		}
		if (sscanf(line, "%lf %lf %lf %lf %lf %lf",
				   &x1, &y1, &x2, &y2, &x3, &y3) != 6) {
			return 1;
		}

		double a1 = 2 * (x2 - x1);
		double b1 = 2 * (y2 - y1);
		double c1 = x1*x1 - x2*x2 + y1*y1 - y2*y2;
		double a2 = 2 * (x3 - x1);
		double b2 = 2 * (y3 - y1);
		double c2 = x1*x1 - x3*x3 + y1*y1 - y3*y3;

		double a = sqrt(pow(x2-x3, 2) + pow(y2-y3, 2));
		double b = sqrt(pow(x3-x1, 2) + pow(y3-y1, 2));
		double c = sqrt(pow(x1-x2, 2) + pow(y1-y2, 2));

		double px = (b1*c2 - b2*c1)/(a1*b2 - a2*b1);
		double py = (c1*a2 - c2*a1)/(a1*b2 - a2*b1);
		double r = (a*b*c) / sqrt((a+b+c)*(-a+b+c)*(a-b+c)*(a+b-c));

		printf("%.3f %.3f %.3f\n", px, py, r);
	}

	return 0;
}

Measured memory_bytes: 1108
#include <stdio.h>
#define N 101

int main(){
  int Adj[N][N],u,k,n,i,j,x;

	scanf("%d",&n);

  for(i=0; i<n; i++){
    for(j=0; j<n; j++)
      Adj[i][j] = 0;
  }

	for(i=0; i<n; i++){
		scanf("%d %d",&u,&k);

    for(j=0; j<k; j++){
      scanf("%d",&x);
      Adj[u-1][x-1] = 1;
    }
	}

  for(i=0; i<n; i++){
    for(j=0; j<n; j++){
      printf("%d",Adj[i][j]);
      if(j!=n-1) printf(" ");
    }
    printf("\n");
  }

  return 0;
}


Measured memory_bytes: 2112
use std::io::stdin;
use std::cmp::{max,min};

fn main(){
    let nm = getvec();
    let (n, m) = (nm[0], nm[1]);
    let ans = min(n, m/2) + max(0, (m-2*n)/4);
    println!("{}", ans)
}

#[allow(dead_code)]
fn getline() -> String {
    let mut s = String::new();
    match stdin().read_line(&mut s){
        Ok(_) => {s.trim().to_string()}
        Err(_) => String::new()
    }
}

#[allow(dead_code)]
fn getvec() -> Vec<i64>{
    let line = getline();
    line.split_whitespace().map(|x| x.parse().unwrap()).collect()
}

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

using ll=long long;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  ll ans = 0;
  rep(i,n)rep(j,n)rep(k,n) ans +=gcd(i+1, gcd(j+1, k+1));
  cout << ans << endl;  
}

Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;

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

  int n, d; cin >> n >> d;
  int x[12][12] = {};
  rep(i, n) rep(j, d) cin >> x[i][j];

  int ans = 0;
  rep(i, n-1) {
    for(int j = i+1; j < n; ++j) {
      int dist = 0;
      rep(k, d) {
        int tmp = abs(x[i][k]-x[j][k]);
        dist += tmp*tmp;
      }
      if((int)sqrt(dist) == sqrt(dist)) ans++;
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
#pragma region _head

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<iomanip>
#include<queue>
#include<stack>
#include<numeric>
#include<utility>
#include<regex>

void Init() {
	std::cin.tie(0); std::ios::sync_with_stdio(false);
	struct Init_caller { Init_caller() { Init(); } }caller;
}

#pragma region _define

#define int LL
#define f(i,a,b) for(LL i=a;i<b;i++)
#define f_vI(v,n) f(i,0,n)cin>>v[i]
#define f_v2I(v1,v2,n) f(i,0,n)cin>>v1[i]>>v2[i]
#define f_v3I(v1,v2,v3,n) f(i,0,n)cin>>v1[i]>>v2[i]>>v3[i]
#define f_vO(v,n) f(i,0,n)cout<<v[i]<<endl
#define ei else if
#define all(a) a.begin(),a.end()
#define size(s) ((LL)s.size())
#define F first
#define S second
#define check() cout<<"! ! !"
#define endl "\n"
#define _y() cout<<"Yes"<<endl
#define _Y() cout<<"YES"<<endl
#define _n() cout<<"No"<<endl
#define _N() cout<<"NO"<<endl
#define INT_INF 1<<29
#define LL_INF 1LL<<60
#define MOD 1000000007

#pragma endregion

#pragma region _using

using namespace std;

using LL = long long;
using st = string;
using vi = vector<LL>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<st>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using qi = queue<LL>;
using qc = queue<char>;
using qs = queue<st>;
using si = stack<LL>;
using sc = stack<char>;
using ss = stack<st>;
using pi = pair<LL, LL>;
using ppi = pair<pi, LL>;
using mll = map<LL, LL>;
using mcl = map<char, LL>;
using vpi = vector<pi>;
using vppi = vector<ppi>;


#pragma endregion

struct edge {
	int from, to, cost;
};

void y_n(bool p) {
	p ? _y() : _n();
}

void Y_N(bool p) {
	p ? _Y() : _N();
}

LL vmax(vi v, LL n) {
	int MAX = 0;
	f(i, 0, n) {
		MAX = max(MAX, v[i]);
	}
	return MAX;
}

LL vmin(vi v, LL n) {
	int MIN = LL_INF;
	f(i, 0, n) {
		MIN = min(MIN, v[i]);
	}
	return MIN;
}

LL gcd(LL a, LL b) {
	LL r;
	while ((r = a % b) != 0) {
		a = b;
		b = r;
	}
	return b;
}
LL lcm(LL a, LL b) {
	return (a / gcd(a, b) * b);
}

//素数判定
bool is_prime(int n) {
	for (int i = 2; i*i <= n; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

//エラトステネスの篩
void sieve(LL n) {
	vb s(n + 1, true);
	f(i, 2, n + 1) {
		for (int j = 2; i*j <= n; j++) {
			s[i*j] = false;
		}
	}
	cout << "2から" << n << "までの素数" << endl;
	f(i, 2, n + 1) {
		if (s[i]) {
			cout << i << " ";
		}
	}
}

//階乗計算
LL factorial(LL n) {
	LL a = 1, ret = 1;
	while (a < n) {
		a++;
		ret *= a;
		ret %= MOD;
	}
	return ret;
}


#pragma endregion 


/*****************************************************************************/
signed main(void) {
	int a, b;
	cin >> a >> b;
	vi sum(1010, 0);
	sum[0] = 0;
	f(i, 1, 1001) {
		sum[i] += sum[i - 1] + i;
	}
	cout << sum[b - a-1] - a;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){

int W,H,x,y,r;

scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);

if(W>=x+r&&x-r>=0&&H>=y+r&&y-r>=0){


printf("Yes\n");


}


else{


printf("No\n");


}

return 0;

}

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

#define M 1000001
#define NIL  (-1)
#define L 14

char H[M][L];

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;
    else return 0;
}

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) {return key % M; }
int h2(int key) {return 1 + (key % (M - 1));}

int find(char str[]) {
    long long key,i,h;
    key = getKey(str);
    for (i = 0;; i++) {
        h = (h1(key) + i * h2(key)) % M;
        if (strcmp(H[h],str) == 0) return 1;
        else if (strlen(H[h]) == 0) return 0;
    }
    return 0;
}

int insert(char str[]) {
    long long key,i,h;
    key = getKey(str);
    for (i = 0; ; i++) {
        h = (h1(key) + i * h2(key)) % M;
        if (strcmp(H[h],str) == 0) return 1;
        else if (strlen(H[h]) == 0) {
            strcpy(H[h],str);
            return 0;
        }
    }
    return 0;
}

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


Measured memory_bytes: 15212
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,m=map(int,input().split())
    A=[[INF]*n for _ in range(n)]
    for i in range(n): A[i][i]=0
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        A[a][b]=c
        A[b][a]=c
    from copy import deepcopy
    C=deepcopy(A)
    # Warshall-Floyd
    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        A[i][j]=min(A[i][j],A[i][k]+A[k][j])
    # count
    B=set()
    for s,i,j in product(range(n),repeat=3):
        if (C[i][j]!=INF) and (i!=j) and (A[s][i]+C[i][j]==A[s][j]):
            B.add((min(i,j),max(i,j)))
    print(m-len(B))

resolve()

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

#define Fast ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define FO freopen("in.txt", "r", stdin)
#define FC freopen("out.txt", "w", stdout)
#define aise cout<<"aise"<<endl
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
#define ll long long
#define all(x) x.begin(), x.end()
#define mset(v, a) memset(v, a, sizeof(v))
#define pll pair< ll, ll >
#define pdd pair< double, double >
#define ff first
#define ss second
#define pi acos(-1.0)
#define mxN 2010
#define inf 1e14
#define MOD 1000000007

int main()

{

    ll n;
    cin >> n;
    vector<ll> v;
    for(ll i = 0; i < n; i++)
    {

        ll x;
        cin >> x;
        ll y = x-(i+1);
        v.pb(y);
    }
    sort(all(v));
    ll b = v[n/2];
    ll ans = 0;
    for(ll i = 0; i < n; i++)
    {

        ans+=abs(v[i]-b);
    }
    cout << ans;
}


Measured memory_bytes: 2420
#include<bits/stdc++.h>
#define llong long long
#define mkpr make_pair
#define x first
#define y second
#define iter iterator
#define riter reversed_iterator
#define y1 Lorem_ipsum_
#define tm dolor_sit_amet_
using namespace std;

inline int read()
{
	int x = 0,f = 1; char ch = getchar();
	for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
	for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
	return x*f;
}

const int mxN = 10;
const int P = 998244353;
char a[mxN+3][mxN+3];
int row[mxN+3],col[mxN+3];
llong f[mxN+3][mxN+3][2],g[mxN+3][mxN+3][2],h[mxN+3][mxN+3];
llong comb[mxN+3][mxN+3],combi[mxN+3][mxN+3];
int n,m;

void updsum(llong &x,llong y) {x+=y-P,x+=(x>>31)&P;}

llong quickpow(llong x,llong y)
{
	if(y==0ll) {return 1ll;}
	llong ret = quickpow(x,y>>1); ret = ret*ret%P; if(y&1ll) ret = ret*x%P;
	return ret;
}
llong mulinv(llong x) {return quickpow(x,P-2);}
void initcomb(int n)
{
	comb[0][0] = 1ll;
	for(int i=1; i<=n; i++) {comb[i][0] = comb[i][i] = 1ll; for(int j=1; j<i; j++) {updsum(comb[i][j]=comb[i-1][j-1],comb[i-1][j]);}}
	for(int i=0; i<=n; i++) for(int j=0; j<=i; j++) {combi[i][j] = mulinv(comb[i][j]);}
}

int main()
{
	initcomb(mxN);
	n = read(),m = read();
	for(int i=0; i<n; i++) {scanf("%s",a[i]); for(int j=0; j<m; j++) a[i][j] = (a[i][j]=='#'?1:0),row[i]|=(a[i][j]<<j),col[j]|=(a[i][j]<<i);}
	llong ans = (1<<m);
	for(int i=0; i<m; i++) {g[0][i][1] = comb[m][i]*(1ll<<i)%P;}
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<m; j++)
		{
			for(int k=1; k<=i; k++)
			{
				llong tmp = (g[i-k][j][0]+g[i-k][j][1]*2ll)*comb[n-i+k][k]%P;
				updsum(f[i][j][0],tmp);
				tmp = g[i-k][j][1]*((1ll<<k)-2ll)%P*comb[n-i+k][k]%P;
				updsum(f[i][j][1],tmp);
			}
			for(int k=1; k<=j; k++)
			{
				llong tmp = (f[i][j-k][0]+f[i][j-k][1]*2ll)*comb[m-j+k][k]%P;
				updsum(g[i][j][0],tmp);
				tmp = f[i][j-k][1]*((1ll<<k)-2ll)%P*comb[m-j+k][k]%P;
				updsum(g[i][j][1],tmp);
			}
			h[i][j] = (f[i][j][0]+f[i][j][1]+g[i][j][0]+g[i][j][1])%P;
			updsum(ans,f[i][j][1]*((1ll<<m-j)-2ll)%P);
			updsum(ans,g[i][j][1]*((1ll<<n-i)-2ll)%P);
		}
	}
	for(int i=1; i<(1<<n); i++)
	{
		for(int j=1; j<(1<<m); j++)
		{
			bool ok = true; int cnt1 = 0,cnt2 = 0;
			for(int k=0; k<n; k++) if(i&(1<<k))
			{
				cnt1++;
				if((row[k]&j)==j||(row[k]&j)==0) {ok = false; break;}
			}
			for(int k=0; k<m; k++) if(j&(1<<k))
			{
				cnt2++;
				if((col[k]&i)==i||(col[k]&i)==0) {ok = false; break;}
			}
			if(!ok) continue;
			updsum(ans,h[n-cnt1][m-cnt2]*combi[n][cnt1]%P*combi[m][cnt2]%P);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
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 ll MOD = 1e9+7;

vector<int> G[100100];
vector<int> L[100100];
bool isvisit[100100];

void dfs(int v, int x){
    isvisit[v] = true;
    for(auto l : L[v]){
        if(l == x) continue;
        for(auto next : G[l]) {
            if(isvisit[next]) continue;
            dfs(next, l);
        }
    }
}

int main(){
    int N, M;
    cin >> N >> M;
    REP(i,N){
        int K;
        cin >> K;
        REP(j,K){
            int l;
            cin >> l;
            l--;
            L[i].push_back(l);
            G[l].push_back(i);
        }
    }

    dfs(0, -1);

    bool ans = true;
    REP(i,N){
        if(!isvisit[i])
            ans = false;
    }

    if(ans)
        cout << "YES" << endl;
    else 
        cout << "NO" << endl;
    return 0;
}


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

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(i, 1, (n))
#define pb push_back
#define f first
#define s second
#define INF 100000000000000000
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<piii> viii;

const int MAXN = 2100;
const ll MOD = 1e9+7;
int h, w;
ll dp[MAXN][MAXN][4];
bool obs[MAXN][MAXN];

int main()
{
    FAST_IO;

    cin >> h >> w;
    FOR(i, 1, h) {
        string s; cin >> s;
        FOR(j, 1, w) {
            if (s[j-1] == '#')
                obs[i][j] = true;
        }
    }

    FOR(i, 1, h) FOR(j, 1, w) {
        if (obs[i][j]) continue;
        FOR(k, 0, 3) dp[i][j][k] = 1;
        dp[i][j][0] += dp[i-1][j][0];
        dp[i][j][1] += dp[i][j-1][1];
    }
    for (int i = h; i > 0; i--) for (int j = w; j > 0; j--) {
        if (obs[i][j]) continue;
        dp[i][j][2] += dp[i+1][j][2];
        dp[i][j][3] += dp[i][j+1][3];
    }

    int ans = 0;
    FOR(i, 1, h) FOR(j, 1, w) {
        int sum = 0;
        FOR(k, 0, 3) sum+= dp[i][j][k];
        //FOR(k, 0, 3) cout << "dp[" << i << "][" << j << "][" << k << "] = " << dp[i][j][k] << "\n";
        ans = max(ans, sum-3);
        //cout << " " << i <<" "<<j<<"  " << sum << endl;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 137472
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=200010;
const ll mod=1e9+7;

vector<int> a(10010,0);
vector<int> b(10010,0);
vector<int> dp(10010,inf);
int h,n;

int rec(int x){
  if(x<=0) return 0;
  if(dp[x]!=inf) return dp[x];
  int res = inf;
  rep(i,n){
    res = min(res, rec(x-a[i]) + b[i]);
  }
  return dp[x] = res;
}

int main(){
  cin >> h >> n;
  rep(i,n){
    cin >> a[i] >> b[i];
  }
  cout << rec(h) << endl;
  return 0;
}

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

int b[100000];

ll haha(int a[], int n){
    if (b[n] != -1) return b[n];
    if(n == 2){
        if(abs(a[2]-a[0])> abs(a[2]-a[1]) + abs(a[1]- a[0])) return abs(a[2]-a[1]) + abs(a[1]- a[0]);
        return abs(a[2]-a[0]);
    }
    if(n==1) return abs ((a[0] - a[1]));
    b[n] = min ((abs(a[n]-a[n-1]) + haha(a, n-1)), (abs(a[n]-a[n-2]) + haha(a, n-2)));
    return b[n];


}

int main(){
    for(int i = 0; i<100000; i++){
        b[i] = -1;
    }
    int n; cin >> n;
    int a[n];
    for(int i =0; i<n; i++){
        cin >> a[i];
    }
    cout << haha(a, n-1);

}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1 << 29;
int hs[100100];
vector<int> dp;

void solve() {
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> hs[i];
    dp.assign(N, INF);
    dp[0] = 0;
    for (int i = 0; i < N - 1; ++i) {
        dp[i + 1] = min(dp[i+1], dp[i] + abs(hs[i+1] - hs[i]));
        if (i + 2 < N) dp[i + 2] = min(dp[i+2], dp[i] + abs(hs[i+2] - hs[i]));
    }
    cout << dp[N - 1] << endl;
}

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


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int b[n];
    for(int i=0;i<n-1;i++)cin >> b[i];
    int a[n];
    long long ans=0;
    a[n-1]=b[n-2];
    for(int i=n-2;i>-1;i--){
        ans+=min(b[i],a[i+1]);
        if(i!=0)a[i]=min(b[i],b[i-1]);
    }
    ans+=b[0];
    cout << ans;
}

Measured memory_bytes: 256
H,W = map(int,input().split())

L = [0]*26
for _ in range(H):
  for a in input():
    L[ord(a)-ord('a')] += 1

m2 = 0
m1 = 0
for n in L:
  if n%4 != 0:
    if n%2 == 0:
      m2 += 1
    else:
      m1 += 1

if H%2 == 0 and W%2==0:
  print('Yes' if m1+m2 == 0 else 'No')
elif H%2==0:
  print('Yes' if m1 == 0 and 2*m2 <= H else 'No')
elif W%2==0:
  print('Yes' if m1 == 0 and 2*m2 <= W else 'No')
else:
  print('Yes' if m1 == 1 and 2*m2 < H+W else 'No')


Measured memory_bytes: 3064
n, m = list(map(int, input().split()))
h = list(map(int, input().split()))
list_ = [1 for _ in range(n)]
for _ in range(m):
    a, b = [i - 1 for i in
            list(map(int, input().split()))]
    if h[a] < h[b]:
        list_[a] = 0
    elif h[b] < h[a]:
        list_[b] = 0
    else:
        list_[a] = 0
        list_[b] = 0
print(sum(list_))


Measured memory_bytes: 20108
n = gets.to_i
array = gets.split(" ").map(&:to_i)
result = Array.new(n, 0)
count = 0

n.downto(1) do |i|
  multiple_count = n / i

  sum = 0
  if multiple_count > 1
    multiple_count.downto(2) do |j|
      sum += result[i * j - 1]
    end
  end

  unless array[i - 1] == sum % 2
    result[i - 1] = 1
    count += 1
  end
end

puts count

result.each.with_index do |re, i|
  print "#{i + 1} " if re == 1
end

Measured memory_bytes: 20484
from itertools import permutations
from math import factorial, sqrt
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,*xy = map(int, read().split())

    XY = []
    for x, y in zip(*[iter(xy)]*2):
        XY.append((x, y))

    ans = 0
    n = factorial(N)
    for p in permutations(range(N)):
        tmp = 0
        for i in range(N-1):
            u, v = p[i], p[i+1]
            a, b = XY[u]
            c, d = XY[v]
            dist = sqrt((a - c)**2 + (b - d)**2)
            tmp += dist
        ans += tmp

    ans /= n
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3188
#include <stdio.h>

void Do(int N){
  int i, s;
  int A[N], B;
  A[0] = 1e9;
  for(i = 0;i < N - 1;i++){
    scanf("%d", &B);
    if(A[i] > B) A[i] = B;
    A[i+1] = B;
  }
  s = 0;
  for(i = 0;i < N;i++) s += A[i];
  printf("%d\n", s);
}

int main(void){
  int N;
  scanf("%d", &N);
  Do(N);
  return 0;
}


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

typedef long long int ll;
#define deb(x) cout << #x << " " << x << endl;
#define debtwo(x,y) cout << #x << " " << x << ", " << #y << " " << y << endl;
#define mod 1000000000000000000

int main()
{
  int n;
  cin >> n;
  vector<ll> arr(n);

  for (int i = 0; i < n; i++) cin >> arr[i];

  sort(arr.begin(), arr.end());
  // for (int i = 0; i < n; i++) cout << arr[i] << " ";
  // cout << endl;
  int c = 0;
  for (int i = 0; i < arr.size() - 2; i++) {
    auto it = upper_bound(arr.begin(), arr.end(), arr[i]);
    if (it == arr.end()) break;
    while (it != arr.end()) {
      int sec = *it;
      it++;
      auto it2 = it;
      //debtwo(arr[i], sec)
      while (it2 != arr.end() && (*it2 < arr[i] + sec)) {
        if (*it2 != sec)c++;
        it2++;
      }
      //deb(c) //1 4 6 6 6 6 8 9 9 10
    }
    // while (i < arr.size() && arr[i + 1] == arr[i]) {
    //   // debtwo(arr[i], arr[i + 1])
    //   // cout << i << endl;
    //   i++;
    // }

  }
  cout << c;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cerr<<(#v)<<":";for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;
#define printVS(vs) cerr<<(#vs)<<":"<<endl;for(auto(s):(vs)){cerr<<(s)<< endl;}
#define printVV(vv) cerr<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;}
#define printP(p) cerr<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cerr<<(#vp)<<":"<<endl;for(auto(p):(vp)){cerr<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

int cost(int state, vi a) {
    int n = a.size();
    int top = a[0];
    int ret = 0;
    rep2(j, 1, n) {
        if (((state >> j) & 1) && a[j] <= top) {
            ret += top + 1 - a[j];
            a[j] = top + 1;
        }
        chmax(top, a[j]);
    }
    return ret;
}

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

    int n, k;
    cin >> n >> k;
    vi a(n);
    rep(i, n) cin >> a[i];

    int ans = inf;
    rep(state, 1 << n) {
        if (__builtin_popcount(state) == k) {
            chmin(ans, cost(state, a));
        }
    }

    cout << ans << endl;
}


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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  int n, a;
  cin >> n;
  deque<ll> dq;

  for (int i = 0; i < n; ++i) {
    cin >> a;
    if (n % 2 == 0) {
      if ((i + 1) % 2 != 0)
        dq.emplace_back(a);
      else
        dq.emplace_front(a);
    } else {
      if ((i + 1) % 2 == 0)
        dq.emplace_back(a);
      else
        dq.emplace_front(a);
    }
  }
  for (auto v : dq) cout << v << " ";

  return 0;
}


Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef vector<int> vec1;
typedef vector<string> vec2;
typedef vector<double> vec3;

int main() {
  int a, b;
  cin >> a >> b;
  if(a == 1) a = 14;
  if(b == 1) b = 14;
  if(a == b) cout << "Draw" << endl;
  else if(a > b) cout << "Alice" << endl;
  else cout << "Bob" << endl;
}

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

int count(int n, int x)
{
	int cnt = 0;
for (int i = 1; i <= n - 2; i++) {
		for (int j = i + 1; j <= n - 1; j++) {
			for (int k = j + 1; k <= n; k++) {
				if (i + j + k == x)cnt++;
			}
		}
	}
	return cnt;
}

int main() {
	int n, x;

	while (1) {
		cin >> n >> x;
		if (n == 0 && x == 0)break;
		cout << count(n, x) << endl;
	}
	return 0;
}


Measured memory_bytes: 3104
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please


int BIT[200001];

void add(int A) {
	while (A > 0) {
		BIT[A]++;
		A -= A & -A;
	}
}

int query(int A) {
	int kotae = 0;
	while (A <= 200000) {
		kotae += BIT[A];
		A += A & -A;
	}
	return kotae;
}

int ne[200001], he[26];


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


	char S[200000];
	scanf("%s", S);
	int N = strlen(S);
	bool k[26] = {};
	rep(i, N) {
		int c = S[i] - 'a';
		ne[i + 1] = he[c];
		he[c] = i + 1;
		k[c] ^= true;
	}
	int kisuu = 0;
	rep(i, 26) if (k[i] & 1) kisuu++;
	if (kisuu > 1) {
		printf("-1");
		return 0;
	}
	int kazu = 0;
	ll kotae = 0;
	int atta = 0;
	rep(i, N) {
		if (kazu * 2 >= N - 1) break;
		if (S[i] >= 'a') {
			int c = S[i] - 'a';
			int kari = he[c] - 1;
			he[c] = ne[he[c]];
			if (i == kari) {
				atta = 1;
				continue;
			}
			kotae += N - kari - 1 - query(kari) + atta;
			S[kari] = 0;
			add(kari);
			kazu++;
		}
	}
	printf("%lld", kotae);

	Would you please return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000+10;
int t[maxn];
int main()
{
    int N,C,K;
    while (scanf("%d%d%d",&N,&C,&K)==3){
         for (int i=0;i<N;i++) scanf("%d",&t[i]);
         sort(t,t+N);
         int cnt = 1;
         int ans = 0;
         int last = t[0]+K;
         for (int i=1;i<N;i++)
         {
             if (t[i]<=last&&cnt<C) cnt++;
             else {
                ans++;
                cnt = 1;
                //cout<<"get one"<<endl;
                last = t[i]+K;
                //cout<<"last "<<last<<endl;
            }
         }
         printf("%d\n",ans+1);
    }
    return 0;
}


Measured memory_bytes: 640
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    AB = []
    for i in range(X):
        for j in range(Y):
            AB.append(A[i] + B[j])
    AB.sort(reverse=True)

    res = []
    for i in range(min(K, len(AB))):
        for j in range(Z):
            res.append(AB[i] + C[j])
    res.sort(reverse=True)

    for i in range(K):
        print(res[i])


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 219276
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

const int V_MAX = 1e5+10;
const int E_MAX = 1e5+10;
struct edge{
  int to;
  ll cost;
};

int V,E;
vector<vector<edge> > G(V_MAX);
vector<ll> dist(V_MAX,0);

void dfs(int cur, int pare){
  rep(i, G[cur].size()){
    if(G[cur][i].to == pare) continue;
    dist[ G[cur][i].to ] = dist[ cur ] + G[cur][i].cost;
    dfs(G[cur][i].to, cur);
  }
}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  cin >> V;
  E = V-1;
  rep(i,E){
    int f,t,c;cin >> f >> t >> c;
    --f;--t;
    G[f].push_back({t,c});
    G[t].push_back({f,c});
  }
  int Q, K;cin >> Q >> K;
  --K;
  dfs(K,-1);
  while(Q--){
    int x,y; cin >> x >> y;
    --x;--y;
    cout << dist[x] + dist[y] << endl;
  }
  return 0;
}


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

// Shrotening
#define fst first
#define snd second
#define pb push_back

// Loop
#define FOR(i,a,b) for(long i=(a);i<(b);++i)
#define RFOR(i,a,b) for(long i=(a);i>=(b);--i)

#define REP(i,a) FOR(i,0,a)
#define RREP(i,a) RFOR(i,a,0)

#define EACH(i,a) for(auto (i)=(a).begin(),_END=(a).end();i!=_END;++i)
#define REACH(i,a) for(auto (i)=(a).rbegin(),_END=(a).rend();i!=_END;++i)

//Algorithm
#define ALL(a) (a).begin(), a.end()
#define RALL(a) (a).rbegin(), a.rend()
#define EXIST(a,x) ((a).find(x)!=(a).end())
#define SORT(a) sort(ALL(a))

//Setting
#define OPT std::cin.tie(0);std::ios::sync_with_stdio(false);

//debug message
bool debug = true;
#define MSG(s)   if(debug){std::cout << s << std::endl;}
#define DEBUG(x) if(debug){std::cout << "debug(" << #x << "): " << x << std::endl;}

//alias
typedef long long LL;
typedef std::vector<char> VC;
typedef std::vector< VC > VCC;
typedef std::vector<int>  VI;
typedef std::vector< VI > VII;
typedef std::vector<long> VL;
typedef std::vector<long long> VLL;
typedef std::pair<int,int> PII;

int H, W;
VCC table;
VII ans;
int dx[] = {-1,0,1,1,1,0,-1,-1};
int dy[] = {-1,-1,-1,0,1,1,1,0};
int main() {
    std::cin >> H >> W;
    table.resize(H, VC(W));
    ans.resize(H, VI(W, 0));

    REP(i, H) {
        REP(j, W) {
            std::cin >> table[i][j];
            if(table[i][j] == '#') {
                REP(k, 8) {
                    int x = j + dx[k];
                    int y = i + dy[k];
                    if(x >= 0 && y >= 0 && x < W && y < H) {
                        ans[y][x]++;
                    }
                }
            }
        }
    }

    REP(i, H) {
        REP(j, W) {
            if(table[i][j] == '#') {
                std::cout << "#";
            } else {
                std::cout << ans[i][j];
            }
        }
        std::cout << "\n";
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)
#define repe(i,s,n)for(ll i = s;i<=n;i++)

int main() {
	ll N, A, B; cin >> N >> A >> B;
	ll cnt = 0;
	repe(i, 1, N) {
		ll sum = 0;
		ll t = i;

		while (t > 0) {
			sum += t % 10;
			t /= 10;
		}

		if (sum >= A && sum <= B) {
			cnt += i;
		}
	}

	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();
		if(a == b) {
			System.out.println(c);
		} else if(a == c) {
			System.out.println(b);
		} else {
			System.out.println(a);
		}
	}
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define endl '\n';
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr double INFD = 1e100;
constexpr ll mod2 = 1000000007;
constexpr ll mod = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
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; }
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// ---------------------------------------------------------------------------

int main(){ 
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N,M;
  cin >> N >> M;
  vector<int> cost(M);
  vector<vector<int>> G(M,vector<int> (N,0));
  for(int i=0; i<M; i++){
    int b;
    cin >> cost[i] >> b;
    for(int j=0; j<b; j++){
      int id;
      cin >> id;
      id--;
      G[i][id] = 1;
    }
  }
  vector<vector<int>> dp(M+1, vector<int> (1<<N,inf));
  dp[0][0] = 0;
  for(int i=0; i<M; i++){
    for(int j=0; j<(1<<N); j++){
      chmin(dp[i+1][j],dp[i][j]);
      if(dp[i][j] == inf) continue;
      int nb = j;
      for(int k=0; k<N; k++){
        if(G[i][k]){
          nb |= (1<<k);
        }
      }
      chmin(dp[i+1][nb],dp[i][j]+cost[i]);
    }
  }
  if(dp[M][(1<<N)-1] == inf){
    cout << -1 << endl;
  }else{
    cout << dp[M][(1<<N)-1] << endl;
  }
  return 0;
}


Measured memory_bytes: 16512
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()

S = [[0]]
ans = []
while S:
    v = S.pop()
    if len(v) == N:
        ans.append(v)
        continue
    else:
        for u in range(max(v)+2):
            S.append(v+[u])

for i,a in enumerate(ans):
    a = list(map(lambda x: chr(x+ord('a')),a))
    ans[i] = ''.join(a)

ans.sort()

for a in ans:
    print(a)

Measured memory_bytes: 84956
import core.stdc.stdio;
import std.algorithm;

void main(){
	int n;
	scanf("%d",&n);
	int[] a = new int[n];
	foreach(ref v;a)
		scanf("%d",&v);
	long[][] dp = new long[][](n,n);
	int l = n%2;
	if(l)
		foreach(i;0..n)
			dp[0][i]=a[i];
	foreach(s;1..n){
		l^=1;
		foreach(i;0..n)
			if(l)
				dp[s][i]=max(dp[s-1][i]+a[(i+s)%n],dp[s-1][(i+1)%n]+a[i]);
			else
				dp[s][i]=a[(i+s)%n]>a[i]?dp[s-1][i]:dp[s-1][(i+1)%n];
	}
	long ans;
	foreach(d;dp[n-1])
		ans=max(d,ans);
	printf("%lld\n",ans);
}

Measured memory_bytes: 34144
#include <iostream>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

const int N = 1e5 + 2;
const long long oo = 1e18L + 5;

int n, k, w[101], v[101];
long long dp[N]; // dp[i]: min weight for items of value dp[i]

int main()
{
    memset(dp, oo, sizeof dp);
    cin >> n >> k;
    int max_value = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> w[i] >> v[i];
        max_value += v[i];
    }
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int cur_value = max_value - v[i]; cur_value >= 0; --cur_value) {
            dp[cur_value + v[i]] = min(dp[cur_value + v[i]], dp[cur_value] + w[i]);
        }
    }
    long long ans = 0;
    for (int i = 0; i <= max_value; ++i) {
        if (dp[i] <= k) {
            ans = max(ans, (long long) i);
        }
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

using ll = long long;

int main() {
  int L;
  cin >> L;
  int l = L;
  vector<tuple<int, int, int>> v;
  for (int i = 0; L >= (1 << i); ++i) {
    if (i) {
      v.push_back(make_tuple(i, i + 1, (1 << (i - 1))));
    }
    if (L & (1 << i)) {
      if (l -= (1 << i)) {
        v.push_back(make_tuple(i + 1, 20, l));
      }
    }
  }
  cout << 20 << " " << v.size() + 19 << endl;
  for (int i = 1; i < 20; ++i) {
    cout << i << " " << i + 1 << " " << 0 << endl;
  }
  for (auto x : v) {
    cout << get<0>(x) << " " << get<1>(x) << " " << get<2>(x) << endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000
int Left[MAX/2+2];
int Right[MAX/2+2];
int cnt;

void merge(int A[], int left, int right, int mid)
{
     int n1 = mid - left;
     int n2 = right - mid;
     for ( int i = 0; i < n1; i++ ) Left[i] = A[i+left];
     Left[n1] = SENTINEL;
     for ( int i = 0; i < n2; i++ ) Right[i] = A[i+mid];
     Right[n2] = SENTINEL;

     int i = 0;
     int j = 0;
     for ( int k = left; k < right; k++ ) {
            cnt++;
            if ( Left[i] <= Right[j] ) A[k] = Left[i++];
            else A[k] = Right[j++];
     }
}

void mergeSort(int A[], int left, int right)
{
    if(left + 1 < right) {
    int mid = (left + right)/2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, right, mid);
    }
}

int main() {
    int A[MAX], n ,i;
    cnt = 0;

    cin >> n;
    for ( i = 0; i < n; i++ ) cin >> A[i];

    mergeSort(A,0,n);

    for ( i = 0; i < n; i++ ) {
        if ( i ) cout << " ";
        cout << A[i];
    }
    cout << endl;

    cout << cnt << endl;

    return 0;
}




Measured memory_bytes: 6956
#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>;
const int MAX = 1000;
const int INF = 1e9;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
#define PI 3.14159265358979323846264338327950L
//setprecision(15)

int main() {
	int N, K; cin >> N >> K;
	vector<int> v(N);
	ll sum = 0;
	rep(i, N) {
		cin >> v[i];
		sum += v[i];
	}
	sort(v.begin(), v.end());
	for (int i = 1; i <= min((int)(v.size()), K); i++) {
		sum -= v[v.size()-i];
	}
	cout << sum << endl;
}

Measured memory_bytes: 4032
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag,
//              tree_order_statistics_node_update>
//     new_data_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)
#define lli long long int
#define llu unsigned long long int
#define fr(va, beg, end) for (lli va = beg; va < end; va++)
#define pb push_back
#define rt return 0
#define endln "\n"
#define all(x) x.begin(), x.end()
// cout << fixed << setprecision(0) << pi <<" "<<npi<<endl;
// gcd function
// __gcd(a, b)
// for max of n elements
// cout<<max({a,b,c,d})<<endl;

lli input(lli n, vector<lli> &ve);
lli input(lli n, vector<lli> &ve) {
    lli val;
    for (lli i = 0; i < n; i++) {
        cin >> val;
        ve.pb(val);
    }
    return 0;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    lli n, a;
    cin >> n;
    vector<lli> v, dp;
    dp.resize(n + 5, -1);
    fr(i, 0, n) {
        cin >> a;
        v.pb(a);
    }
    dp[0] = 0;

    fr(i, 0, n) {
        lli val1 = 0, val2 = 0;
        if (i + 1 < n) {
            val1 = abs(v[i + 1] - v[i]);
        }
        if (i + 2 < n) {
            val2 = abs(v[i + 2] - v[i]);
        }
        if (dp[i + 1] != -1) {
            dp[i + 1] = min(dp[i + 1], val1 + dp[i]);
        } else {
            dp[i + 1] = val1 + dp[i];
        }
        if (dp[i + 2] != -1) {
            dp[i + 2] = min(dp[i + 2], val2 + dp[i]);
        } else {
            dp[i + 2] = val2 + dp[i];
        }
    }

    // fr(i, 0, n) {
    //     cout << dp[i] << " ";
    // }
    // cout << endl;
    cout << dp[n - 1] << endl;
    rt;
}


Measured memory_bytes: 2168
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <cmath>
#include <climits>
#include <iomanip>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;

int main() {
    ll n, *a, m; cin >> n >> m;   
    a = new ll[m];
    ll s = 0;
    for (int i = 0; i < m; i++) {
        cin >> a[0];
        s+= a[0];
    }

    if (s <= n)
        cout << n-s << endl;
    else 
        cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 3636
list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1,5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
a = int(input())
print(list[a - 1])

Measured memory_bytes: 3060
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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 (a>b) { a=b; return 1; } return 0; }
V<string> s;
int h,w;
int ans;
int memo[101][101];
void dfs(int y,int x,int cnt){
    if(cnt>=memo[y][x])return;
    memo[y][x]=cnt;
    if(y==h-1&&x==w-1)return;
    if(y+1<h){
       if(s[y][x]=='.'&&s[y+1][x]=='#') dfs(y+1,x,cnt+1);
       else dfs(y+1,x,cnt);
    }
    if(x+1<w){
         if(s[y][x]=='.'&&s[y][x+1]=='#')dfs(y,x+1,cnt+1);
         else dfs(y,x+1,cnt);
    }
}
int main(){
cin>>h>>w;
ans=INT_MAX;
s.resize(h);
for(int i=0;i<h;i++)for(int j=0;j<w;j++)memo[i][j]=INT_MAX;
for(int i=0;i<h;i++)cin>>s[i];
dfs(0,0,(s[0][0]=='#'?1:0));
cout<<memo[h-1][w-1]<<"\n";
}

Measured memory_bytes: 384
N = int(input())
A = list(map(int, input().split()))
flag = True
for a in A:
    if a % 2 == 0:
        if a % 3 == 0 or a % 5 == 0:
            continue
        else:
            flag = False

if flag:
    print('APPROVED')
else:
    print('DENIED')




Measured memory_bytes: 61976
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define rrep(i, a, n) for (int i = (int)(a); i >= (int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) \
  rep(f, 0, (x.size() - 1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define debug2(x, y)                       \
  cerr << "(" << #x << "," << #y << ") = " \
       << "(" << x << "," << y << ")\n"
#define all(x) x.begin(), x.end()
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MX = 1e5 + 5, INF = 5 << 28, MOD = 1e9 + 7;

string S;
int K;
void input() {
  cin >> S;
  cin >> K;
  ;
  ;
}
void solve() {
  int n = S.size();

  if (n == 1) {
    cout << (K / 2) << endl;
    return;
  }

  bool allone = true;
  for (int i = 1; i < n; ++i) {
    if (S[i - 1] != S[i]) allone = false;
  }
  if (allone) {
    cout << (n * K) / 2 << endl;
    return;
  }

  string s2 = S + S;

  int cnt = 0;
  int state = 0;

  for (int i = 1; i < n; ++i) {
    if (state == 0) {
      if (S[i - 1] == S[i]) {
        state = 1;
        cnt++;
      }
    } else if (state == 1) {
      if (S[i - 1] == S[i]) {
        state = 0;
      } else {
        state = 0;
      }
    }
  }

  int cnt2 = 0;
  state = 0;
  for (int i = 1; i < 2 * n; ++i) {
    if (state == 0) {
      if (s2[i - 1] == s2[i]) {
        state = 1;
        cnt2++;
      }
    } else if (state == 1) {
      if (s2[i - 1] == s2[i]) {
        state = 0;
      } else {
        state = 0;
      }
    }
  }
  int ans = (cnt + (cnt2 - cnt) * (K - 1));
  cout << ans << endl;
}
signed main() {
  input();
  solve();
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <queue>
using namespace std;
int main(){
	int N, K, Q; cin >> N >> K >> Q; 
	int A[100010] = {}; 
	for(int i = 0; i < Q; i++){
		int a; cin >> a; A[a] ++; 
	}
	for(int i = 1; i <= N; i++){
		if(K - Q + A[i] > 0) cout << "Yes" << endl; 
		else cout << "No" << endl; 
	}
}

Measured memory_bytes: 1024
#include<stdio.h>
#define datamax 500001
#define banpei 1000000001
int left[datamax/2 +1];
int right[datamax/2 + 1];
int cnt;
void merge(int *,int,int,int,int);
void mergeSort(int *,int,int,int);
  int main(){
  int a[datamax],n,i;
  cnt = 0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  mergeSort(a,n,0,n);
  for(i=0;i<n;i++){
    if(i)printf(" ");
    printf("%d",a[i]);
  }
  printf("\n%d\n",cnt);

  return 0;
}

void merge(int a[],int n, int leftnum ,int mid,int rightnum){
  int n1,n2,i=0,j=0,k;
   n1 = mid - leftnum;
   n2 = rightnum - mid;
  for(i=0;i<n1;i++)left[i] = a[leftnum + i];
  for(i=0;i<n2;i++)right[i] = a[mid + i];
  left[n1] = right[n2] = banpei;
  i=0;
  for(k=leftnum;k<rightnum;k++){
    cnt++;
    if(left[i] <= right[j]){
      a[k] = left[i++]; 
    }else{
      a[k] = right[j++];
    }
  }
}

void mergeSort(int a[],int n,int leftnum,int rightnum){
  int mid;
  if(leftnum +1 < rightnum){
    mid = (leftnum + rightnum) / 2;
    mergeSort(a,n,leftnum,mid);
    mergeSort(a,n,mid,rightnum);
    merge(a,n,leftnum,mid,rightnum);
  }
}





Measured memory_bytes: 5604