akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;
using pll=pair<ll,ll>;

#define fi first
#define se second
#define pb push_back
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define MOD 1000000007

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

int main() {
	int N;
	cin >> N;
	int maxi = -1;
	int ans;
	rep(i,N) {
		int t = i+1;
		int s = 0;
		while(1) {
			if(t%2 == 0) t/=2,s++;
			else break;
		}
		if(maxi < s) maxi = s,ans = i+1;
	}
	cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>

const double pi = 3.14159265359;

struct vec {
	double x;
	double y;
	const vec operator +(const vec &r) const {
		vec t;
		t.x = this->x + r.x;
		t.y = this->y + r.y;
		return t;
	}
	const vec operator -(const vec &r)const {
		vec t;
		t.x = this->x - r.x;
		t.y = this->y - r.y;
		return t;
	}
};

vec shift(vec o, vec p) {
	return  o - p;
}

vec rotate(vec v, double alpha) {
	using namespace std;
	vec t;
	t.x = cos(alpha) * v.x - sin(alpha) * v.y;
	t.y = sin(alpha) * v.x + cos(alpha) * v.y;
	return t;
}

vec LfG(vec o, double a, vec G) {
	vec L;
	L = shift(o, G);
	L = rotate(L, a);
	return L;
}

vec GfL(vec o, double a, vec L) {
	vec G;
	G = rotate(L, -a);
	G = shift(o, G);
	return G;
}


vec get_s(vec p1, vec p2) {
	vec s;
	s.x = p1.x * 2 / 3 + p2.x * 1 / 3;
	s.y = p1.y * 2 / 3 + p2.y * 1 / 3;
	return s;
}

vec get_t(vec p1, vec p2) {
	vec t;
	t.x = p1.x * 1 / 3 + p2.x * 2 / 3;
	t.y = p1.y * 1 / 3 + p2.y * 2 / 3;
	return t;
}

double get_alpha(vec v1, vec v2) {
	double l_v1 = std::sqrt(v1.x * v1.x + v1.y * v1.y);
	double l_v2 = std::sqrt(v2.x * v2.x + v2.y * v2.y);
	return std::acos((v1.x*v2.x + v1.y*v2.y) / (l_v1 * l_v2));
}

void print(vec v) {
	std::cout << v.x << " " << v.y << std::endl;
}


void koch(vec p1, vec p2, int c) {
	if (c == 0)
		return;
	c--;

	vec s = get_s(p1, p2);
	vec t = get_t(p1, p2);

	double a = get_alpha(s, t);
	vec ls = LfG(s, a, s);
	vec lt = LfG(s, a, t);
	vec lu = rotate(lt, pi / 3);
	vec u = GfL(s, a, lu);

	koch(p1, s, c);
	print(s);
	koch(s, u, c);
	print(u);
	koch(u, t, c);
	print(t);
	koch(t, p2, c);
}



int main() {


	std::cout << std::fixed;

	int n;
	std::cin >> n;

	vec p1 = { 0,0 };
	vec p2 = { 100, 0 };

	print(p1);
	koch(p1, p2, n);
	print(p2);

	return 0;
}

Measured memory_bytes: 3536
#include <stdio.h>
#define N 36

typedef struct{
    char alp;
    int num,o;
} card;

card c[N],arr[N];
int n;

void bubble(){
    int i;
    card tmp;
    for(i=0;i<n;i++){
        arr[i]=c[i];
    }
    
    int flag=1;
    while(flag){
      flag=0;
      for(i=n-1;i>0;i--){
	    if(arr[i].num<arr[i-1].num){
	        tmp=arr[i];
	        arr[i]=arr[i-1];
	        arr[i-1]=tmp;
	        flag=1;
	        }
        }     
    }
}

void select(){
    int i,j,minj;
    card tmp;
    
    for(i=0;i<n;i++){
        arr[i]=c[i];
    }
    
    for(i=0;i<n;i++){
        minj=i;
        for(j=i;j<n;j++){
	        if(arr[minj].num>arr[j].num) minj=j;
        }
        if(minj!=i){
	        tmp=arr[i];
	        arr[i]=arr[minj];
	        arr[minj]=tmp;
        }
    }

}

void print(){
    int i,s=1;
    for(i=0;i<n;i++){
      if(i!=0){
          if(arr[i-1].num==arr[i].num && arr[i-1].o>arr[i].o)
            s=0;
          printf(" ");
          
      }
      printf("%c%d",arr[i].alp,arr[i].num);
    }
    if(s) printf("\nStable\n");
    else  printf("\nNot stable\n");
}

int main(void){
    int i,tmp,flag=1,b;
    char a;
    
    scanf("%d ",&n);
    for(i=0;i<n;i++){
      scanf("%c%d ",&c[i].alp,&c[i].num);
      c[i].o=i;
    }
    
    bubble();
    print();
    
    select();
    print();
    
    return 0;
}



Measured memory_bytes: 2148
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n, a, b, sum = 0;
int main()
{
	cin >> n >> a >> b;
	sum = n / (a+b) * a;
	if(n % (a+b) >= a)
		sum += a;
	else
		sum += n % (a+b);
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

ans = 0
for i in range(0, len(A)-1):
  for j in range(len(A)-2, i-1, -1):
    if A[j] > A[j+1]:
      A[j], A[j+1] = A[j+1], A[j]
      ans += 1

print(" ".join(list(map(str, A))))
print(ans)


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

int main (void){
  int n;
  cin >> n;
  vector<int>v(n);
  for(int i = 0; i < n; i++){
    int x;
    cin >> x;
    v[i] = x;
  }
  sort(v.begin(), v.end());
  
  double ans = static_cast<double>(v[0]);
  
  for(int i = 1; i < n; i++){
    ans = (ans + v[i]) / 2.;
  }
  cout << ans;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(void){
    int n,q;
    cin>>n>>q;
    int m=n;
    int a[300010];
    while(m--)cin>>a[m];
    sort(a,a+n);
    for(int i=0;i<q;i++){
        int ans=0;
        int x;
        cin>>x;
        for(int j=x;j<300000;j+=x)ans=max(ans,a[lower_bound(a,a+n,j)-a-1]%x);
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 2348
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const ll inf=1e9+7;
const ll INF=1e18;

int main(){
    int n;cin>>n;
    vll ans(n);
    vll a(n);
    rep(i,n){
        cin>>a[i];
        if(i%2==0)ans[0]+=a[i];
        else ans[0]-=a[i];
    }
    ans[0]/=2;
    rep(i,n-1)ans[i+1]=a[i]-ans[i];
    rep(i,n-1)cout<<2*ans[i]<<" ";
    cout<<2*ans[n-1]<<endl;
}

Measured memory_bytes: 2944
#include<iostream>
#include<string>
using namespace std;
int a[30];
string work()
{
	for(int i=1;i<=26;i++)
	if(a[i]&1) return "No";
	return "Yes";
}
int main()
{
	char c=getchar();
	while(c<='z'&&c>='a')
	{
		a[c-'a'+1]++;
		c=getchar();
	}
	cout<<(string)work()<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  int r;
  cin >> n;
  
  if(n % 1000 == 0){
     cout << 0 << endl;
  }else{
    r = 1000 - (n % 1000); 
    cout << r << endl;
  }
}

Measured memory_bytes: 3568
def main():
# input
    N, K = map(int, input().split())
    b = input()

# loop
    num = 0
    for i in range(len(b)-1):
        if b[i] != b[i+1]:
            num += 1
    print(min(N-1, N-1-num+2*K))

if __name__ == '__main__':
    main()


Measured memory_bytes: 39408
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(a) int((a).size())

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    ll h,a;
    cin>>h>>a;
    if(h%a) cout<<h/a + 1;
    else cout<<h/a;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define cincout ios::sync_with_stdio(false)
#define mp make_pair
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef map<int, int> mii;

int n;
ll a[100005];
ll pre[100005];
ll pos[100005];

ll gcd(ll a, ll b){
	if(b==0) return a;
	return gcd(b,a%b);
}

int main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	pre[1]=a[1];
	pos[n]=a[n];
	for(int i=2;i<=n;i++){
		pre[i] = gcd(pre[i-1],a[i]);
	}
	for(int i=n-1;i>=1;i--){
		pos[i] = gcd(pos[i+1],a[i]);
	}
	ll ans = 0;
	for (int i=1; i<=n; i++) {
		ll tmp = 0;
		if(i>1) tmp = gcd(tmp, pre[i-1]);
		if(i<n) tmp = gcd(tmp, pos[i+1]);
		ans = max(ans, tmp);
	}
	cout << ans <<endl;
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

string s;
bool answered;

void dfs(int d, int u){
	if(d == s.length()-1){
		int t = s[0] - '0';
		for(int i = 0; i < s.length()-1; i++){
			if(u & (1 << i)){
				t += s[i+1] - '0';
			}else{
				t -= s[i+1] - '0';
			}
		}

		if(t == 7 && !answered){
			cout << s[0];
			for(int i = 0; i < s.length()-1; i++){
				if(u & (1 << i)){
					cout << '+' << s[i+1];
				}else{
					cout << '-' << s[i+1];
				}
			}
			cout << "=7" << endl;
			answered = true;
			return;
		}
		return;
	}

	int b = (1 << d);
	dfs(d+1, u);
	dfs(d+1, u+b);
}

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

	cin >> s;
	answered = false;
	dfs(0, 0);
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val p = readLine()!!.split(' ').map { s -> s.toLong() }
    var cnt = 0L
    (1..n-2).forEach{
        index ->
            cnt += if ((p[index-1] < p[index] && p[index] < p[index+1]) || (p[index+1] < p[index] && p[index] < p[index-1])) 1L else 0L 
    }
    println(cnt)
}

Measured memory_bytes: 38236
n, x, y = input().split()
n, x, y = int(n), int(x)-1, int(y)-1
d = [[abs(i-j) for i in range(n)] for j in range(n)]
for i in range(x+1):
    for j in range(y, n):
        d[i][j] -= y-x-1
    for j in range(y-1, x+(y-x)//2, -1):
        d[i][j] = d[i][j+1]+1
for i in range(x+1, x+(y-x)//2):
    d[i][y] = d[i][x] + 1
    for j in range(y+1, n):
        d[i][j] = d[i][j-1]+1
    for j in range(y-1, x+(y-x)//2+(i-x), -1):
        d[i][j] = d[i][j+1]+1
apar = [0 for i in range(n)]
for i in range(n-1):
    for j in range(i+1, n):
        apar[d[i][j]] += 1
for i in range(1, n):
    print(apar[i])


Measured memory_bytes: 132368
N = int(input())
D1 =[]
D2 =[]
for i in range(N):
    a,b = map(int,input().split())
    D1.append(a)
    D2.append(b) 
ans = "No"
for i in range(N-2):
    if D1[i]==D2[i]:
        if D1[i+1]==D2[i+1]:
            if D1[i+2]==D2[i+2]:
                ans ="Yes"
print(ans)

Measured memory_bytes: 9216
#include<bits/stdc++.h>
#define eps 0.000000001
using namespace std;
typedef long double ld;
typedef pair<int,int> p;
typedef pair<ld,p> P;

int n;
ld px[200],py[200],pz[200],vx[200],vy[200],vz[200],r[200],vr[200];

ld getlen(int a,int b,ld M){
  ld ax=px[a]+vx[a]*M,ay=py[a]+vy[a]*M,az=pz[a]+vz[a]*M,ar=r[a]-vr[a]*M;
  ld bx=px[b]+vx[b]*M,by=py[b]+vy[b]*M,bz=pz[b]+vz[b]*M,br=r[b]-vr[b]*M;
  ld dx=ax-bx,dy=ay-by,dz=az-bz;
  return sqrt(dx*dx+dy*dy+dz*dz)-(ar+br);
}

ld check(int a,int b){
  ld L=0,R=100,M;
  int s=0;
  while(s++<50){
    M=(L+R)/2;
    ld len=getlen(a,b,M),len1=getlen(a,b,M+eps);
    if(len<len1||len<0)R=M;
    else L=M;
  }
  if(getlen(a,b,R)>0)return 100;
  return R;
}

int main(){
  while(cin>>n,n){
    for(int i=0;i<n;i++)
      cin>>px[i]>>py[i]>>pz[i]>>vx[i]>>vy[i]>>vz[i]>>r[i]>>vr[i];
    priority_queue<P,vector<P>,greater<P> > q;
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++)
	q.push(P(check(i,j),p(i,j)));
      q.push(P(r[i]/vr[i],p(i,i)));
    }
    ld used[200]={};
    while(!q.empty()){
      ld t=q.top().first;
      int a=q.top().second.first,b=q.top().second.second;
      q.pop();
      if(used[a]||used[b])continue;
      used[a]=used[b]=t;
    }
    for(int i=0;i<n;i++)printf("%.10Lf\n",used[i]);
  }
  return 0;
}

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

int main(){
    int h,w;cin>>h>>w;vector<vector<char>> A(105,vector<char>(105)),B(105,vector<char>(105)),C(105,vector<char>(105));int countw=0,counth=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>A.at(i).at(j);
		}
    }
	for(int i=0;i<h;i++){
		int count=0;
		for(int j=0;j<w;j++){
			if(A.at(i).at(j)=='.') count++;
        }
        if(count!=w){
	        for(int j=0;j<w;j++){
    	    	B.at(counth).at(j)=A.at(i).at(j);
        	}
			counth++;
        }
	}
    for(int j=0;j<w;j++){
        int count=0;
        for(int i=0;i<counth;i++){
            if(B.at(i).at(j)=='.') count++;
        }
        if(counth!=count){
            for(int i=0;i<counth;i++){
	            C.at(i).at(countw)=B.at(i).at(j);
        	}
			countw++;
    	}
	}
    for(int i=0;i<counth;i++){
        for(int j=0;j<countw;j++){
            cout<<C.at(i).at(j);
        }
        cout<<endl;
    }
}

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

using namespace std;

const int N = 1e6 + 6;
int t[N];

int main() {
  int n, k, c;
  scanf("%d %d %d", &n, &c, &k); 
  for (int i = 0; i < n; i++)
    scanf("%d", t+i);
  sort(t, t+n);
  int ans = 0, start = -1, cnt = 0;
  for (int i = 0; i < n; i++) {
    if (start == -1 || cnt >= c)
      start = t[i], cnt = 0, ans++;
    if (start + k < t[i])
      start = t[i], cnt = 0, ans++;
    cnt++;
  }
  printf("%d\n", ans);
  return 0;
}

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

#define MAX_STRING	( 65536 )

void sortStr( char* input, char* output );

int main( void )
{
	char string[ MAX_STRING + 1 ];
	char output[ MAX_STRING + 1 ];
	
	int n;
	int i;
	
	while( 1 )
	{
		if( scanf( "%d", &n ) == EOF )break;;
		if( n == 0 )break;
		scanf( "%s", string );
		
		for( i = 0; i < n; i++ )
		{
			sortStr( string, output );
			strcpy( string, output );
		}
		printf( "%s\n", output );
	}
	
	return (0);
}

void sortStr( char* input, char* output )
{
	char tmp[ MAX_STRING + 1 ];
	int numOfRepeat;
	char strOfRepeat[4];
	char nowChar;
	char nowStr[2] = {'\0', '\0'};
	int i;
	int j;
	
	strcpy( tmp, "" );
	nowChar = -1;
	for( j = 0; input[j] != '\0'; j++ )
	{
		if( nowChar == -1 )
		{
			nowChar = input[j];
			nowStr[0] = input[j];
			numOfRepeat = 1;
		}
		else
		{
			if( nowChar != input[j] )
			{
				sprintf( strOfRepeat, "%d", numOfRepeat );
				strcat( tmp, strOfRepeat );
				strcat( tmp, nowStr );
					
				nowChar = input[j];
				nowStr[0] = input[j];
				numOfRepeat = 1;
			}
			else
			{
				numOfRepeat++;
			}
		}
	}
	sprintf( strOfRepeat, "%d", numOfRepeat );
	strcat( tmp, strOfRepeat );
	strcat( tmp, nowStr );
	
	strcpy( output, tmp );
	//printf( "%s\n", output );
}

Measured memory_bytes: 764
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

int main() {
	int n, m;
	string s;
	cin >> n;
	map<string, int> dict;
	for (int i = 0; i < n; i++) {
		cin >> s;
		dict[s]++;
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> s;
		dict[s]--;
	}
	int ans = 0;
	for (map<string, int>::iterator i = dict.begin(); i != dict.end(); i++)
		ans = max(ans, i->second);
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<set>
#include<iostream>

using namespace std;

int main()
{
  while(true)
    {
      int m;
      cin >> m;
      if(!m)
	break;

      int value[10001];
      for(int i=0;i<10001;i++)
	value[i] = 0;

      set<int> index;
      index.insert(0);
      value[0] = 1;

      for(int i=0;i<m;i++)
	{
	  int a,b;
	  cin >> a >> b;
	  set<int> next = index;
	  int next_vakue[10000];
	  for(int i=0;i<10001;i++)
	    next_vakue[i] = value[i];
	  for(set<int>::iterator it = index.begin();it != index.end();it++)
	    for(int j=1;j<=b;j++)
	      {
		if(next.find((*it)+j*a) == next.end())
		  next.insert((*it)+j*a);
		value[(*it)+j*a]+=next_vakue[(*it)];
	      }		

	  
	  index = next;
	}

      cin >> m;
      for(int i=0;i<m;i++)
	{
	  int n;
	  cin >> n;
	  cout << value[n] << endl;
	}

    }
  return 0;
}

Measured memory_bytes: 1452
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    S=ST()
    Q=I()
    query = []
    for q in range(Q):
        *s, = ST().split()
        query.append(s)
    left = deque()
    right = []
    rev = False
    for q in query:
        if q[0] == "1":
            rev ^= True
        else:
            to_right = int(q[1]) - 1
            s = q[2]
            if rev ^ (q[1] == "1"):
                left.appendleft(q[2])
            else:
                right.append(q[2])
    ans = "".join(left) + S + "".join(right)
    if rev:
        ans = ans[::-1]
    
    print(ans)
if __name__ == '__main__':
    main()

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

int main(){
ll N;
cin>>N;
cout<<(N-1)/2<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

bool valid(int A, int C) {
  // C = A - B
  int B = A - C;
  return (B > 0 && B < A);
}

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int N;
  while (cin >> N) {
    vector<ll> S(N);
    for (ll& x : S) cin >> x;
    ll res = 0;
    vector<int> used(N, 0);
    for (int C = 1; C < N; C++) {
      ll sum = 0;
      int l = 0, r = N - 1;
      used[l] = used[r] = C;
      for (int A = N - 1 - C; ; A -= C) {
        l += C;
        r -= C;
        if (l > N - 1 || used[l] == C) break;
        used[l] = C;
        if (r < 0 || used[r] == C) break;
        used[r]  = C;
        sum += S[l] + S[r];
        if (valid(A, C)) {
          chmax(res, sum);
        }
      }
    }
    cout << res << endl;
  }
  return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long unsigned i,N,sum=0;
    cin>>N;

    for(i=1;i<=N;i++){
        if(i%3!=0&&i%5!=0){
            sum=sum+i;
        }
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3636
def A():
    print(int(input())**3)

def B():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()]

    points = B[A[0]-1]
    previous = A[0]-1
    #print(points)
    for i in range(1, N):
        points += B[A[i]-1]
        if A[i]-1 == previous+1:
            points += C[previous]
        #print(points)
        previous = A[i]-1
    
    print(points)
B()

Measured memory_bytes: 3064
n, m = map(int, input().split())

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

from collections import deque

ans = [-1] * n
def bfs(u):
   queue = deque([u])
   d = [None] * n
   d[u] = 0
   while queue:
      v = queue.popleft()
      for i in g[v]:
         if d[i] is None:
            d[i] = d[v] + 1
            queue.append(i)
            ans[i] = v + 1

   return d

d = bfs(0)
ans.pop(0)
if -1 in ans:
   print('No')
else:
   print('Yes')
   for x in ans:
      print(x)


Measured memory_bytes: 37832
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e5 + 7;
const int Inf = 1 << 30;
const ll INF = 1ll << 60;
int n;
int a[10], b[10];
bool vis[10];
int ans[10];
int cnt, res1, res2;

void Dfs(int x) {
	if(x == n + 1) {
		cnt++;
		bool chk = 1;
		for(int i = 1; i <= n; i++) {
			if(ans[i] != a[i]) {
				chk = 0;
				break;
			}
		}
		if(chk) res1 = cnt;
		chk = 1;
		for(int i = 1; i <= n; i++) {
			if(ans[i] != b[i]) {
				chk = 0;
				break;
			}
		}
		if(chk) res2 = cnt;
	}
	for(int i = 1; i <= n; i++) {
		if(!vis[i]) {
			vis[i] = 1;
			ans[x] = i;
			Dfs(x + 1);
			vis[i] = 0;
		}
	}
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
	Dfs(1);
	printf("%d\n", abs(res1 - res2));
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) container.begin(), container.end()
#define RALL(container) container.rbegin(), container.rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const double EPS = 1e-8;
const int MOD = 1000000007;


const ll INF = 1ll<<40;
int n, A, B;
ll r[200], s[200];
ll sum[200];

int solve(int player, int i, ll nut);

int dfs(int player, int i, ll nut){
	if(i == n) return 0;
	int res = s[i] + sum[n] - sum[i+1] - solve(!player, i+1, -(nut + r[i]));
	if(nut > 0) res = max(res, solve(player, i+1, (nut - r[i] - 1)));
	return res;
}

map<ll, int> memo[2][200];

void fillTable(int player, int i){
	map<ll, int> &tar = memo[player][i];
	int low = tar[-INF] = dfs(player, i, -INF/2);
	int hi = tar[INF] = dfs(player, i, INF/2)+1;
	for(int j=low+1;j<hi;j++){
		ll l=-INF, r = INF;
		while(l<r-1){
			ll med = (l+r)/2;
			if(dfs(player, i, med) < j) l = med;
			else r = med;
		}
		j = tar[r] = dfs(player, i, r);
	}
}

int solve(int player, int i, ll nut){
	if(i == n) return 0;
	if(memo[player][i].empty()) fillTable(player, i);
	auto it = (memo[player][i].upper_bound(nut));
	return (--it)->second;
}

main(){
	ios::sync_with_stdio(false);
	cin >> n >> A >> B;
	REP(i, n){
		cin >> r[i] >> s[i];
		sum[i+1] = sum[i] + s[i];
	}
	int res = solve(0, 0, A-B);
	cout << res << " " << sum[n] - res << endl;
	return 0;
}

Measured memory_bytes: 1432
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define MAXN 1000
#define MOD 1e9+5

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef long long ll;

int main(){
    int H, A;
    cin >> H >> A;
    int ans = H/A;
    //cout << ans << endl;
    ans += (H%A)? 1 : 0;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
use std::io;

fn gets() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf
}

fn main() {
    let line = gets();
    let mut it = line
        .trim()
        .split_whitespace()
        .map(|x| x.parse::<u32>().unwrap());
    let (mut a, b, mut c, d) = (
        it.next().unwrap(),
        it.next().unwrap(),
        it.next().unwrap(),
        it.next().unwrap(),
    );
    loop {
        if c <= b {
            println!("Yes");
            return;
        } else {
            c -= b;
        }
        if a <= d {
            println!("No");
            return;
        } else {
            a -= d;
        }
    }
}


Measured memory_bytes: 2112
n = int(input()) - 1
a = list(map(int, input().split()))

count = 0
flag  = 1

while flag:
    flag = 0
    for i in range( n, 0, -1 ):
        if a[i] < a[i-1]:
            t = a[i]
            a[i] = a[i-1]
            a[i-1] = t
            count += 1
            flag = 1

print(*a)
print(count)

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

int main(){
 int m,f,r;

 while(1){
  cin >> m >> f >> r ;
  if(m==-1&&f==-1&&r==-1)break;
  if(m==-1||f==-1)cout << "F" << endl;
  else if(m+f>=80)cout << "A" << endl;
  else if(m+f>=65)cout << "B" << endl;
  else if(m+f>=50)cout << "C" << endl;
  else if(m+f>=30){
   if(r>=50)cout << "C" << endl;
   else cout << "D" << endl;
  }
  else cout << "F" << endl;
 }

 return 0;
}

Measured memory_bytes: 3076
import sys


def calc(a: int, op: str, b: int) -> int:
    if op == '+':
        return a + b
    if op == '-':
        return a - b
    if op == '*':
        return a * b
    return int(a / b)

def resolve():
    for line in sys.stdin:
        a, op, b = map(str, line.split())
        a = int(a)
        b = int(b)

        if op == '?':
            break

        # No using eval
        print(calc(int(a), op, int(b)))


resolve()


Measured memory_bytes: 5604
using System;
using System.Numerics;
using System.Linq;
using System.Collections.Generic;
using System.Text;

namespace debug
{
    class ProgramD
    {
        static void Main(string[] args)
        {

            //入力
            int n = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();
            int Wc = 0;
            int Ec = 0;

            for(int i = 0; i < n;i++)
            {
                if (s[i] == 'W')
                    Wc++;
                else
                    Ec++;
            }

            int[] ans = new int[n];
            if(s[0] == 'W')
               ans[0] = Ec;
            else
               ans[0] = Ec - 1;

            for (int i = 1; i < n; i++)
            {
                if (s[i - 1] == 'E' && s[i] == 'E')
                    ans[i] = ans[i - 1] - 1;
                else if (s[i - 1] == 'W' && s[i] == 'W')
                    ans[i] = ans[i - 1] + 1;
                else
                    ans[i] = ans[i - 1];

            }

            Console.WriteLine(ans.Min());

        }

        
    }

}


Measured memory_bytes: 13408
if __name__ == "__main__":
    N = int(input())
    bs = list(map(int, input().split()))

    operations = []
    for i in range(N):
        j_remove = -1
        for j in range(N-i):
            if bs[j] == j+1:
                j_remove = j
        if j_remove == -1:
            print("-1")
            exit()
        operations.append(bs.pop(j_remove))
    for n in reversed(operations):
        print(n)


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)

#define DEBUG

#ifdef DEBUG
#define var_dump(...) fprintf(stdout, __VA_ARGS__)
#define dump(a) cout << a << "\n";
#else
#define var_dump(...) 42
#define dump(a) 42
#endif

typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

// https://beta.atcoder.jp/contests/abc082/tasks/abc082_b

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

    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    reverse(t.begin(), t.end());

    if (s < t) {
        cout << "Yes" << "\n";
    } else {
        cout << "No" << "\n";
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <cmath>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <iomanip>

using namespace std;
typedef long long ll;

void imie() {
	cout << "hello" << "\n";
}

const ll INF = 1e18 + 5;

const int mXN = 100005;
int vis[mXN][2];

int dfs(int u, const vector<vector<int>>& dp) {
	if (vis[u][1] == 1) return vis[u][0];
	
	int ans = 0;
	for (int i = 0; i < dp[u].size(); i++) {
		ans = max(ans, dfs(dp[u][i]-1, dp)+1);
		vis[u][0] = ans;
		vis[u][1] = 1;
	}
	
	return ans;
}


void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> dp(n, vector<int>());
	vector<pair<int, int>> p(n);
	for (int i = 0; i < m; i++) {
		int A, B;
		cin >> A >> B;
		dp[A - 1].push_back(B);
		p[A - 1].first++;
	}

	for (int i = 0; i < n; i++) {
		p[i].second = i;
	}

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

	int ans1 = 0;
	//call dfs function
	for (int i = 0; i < n; i++) {
		if (p[i].first == 0) {
			vis[p[i].second][0] = 0;
			vis[p[i].second][1] = 1;
		}
		else {
			int tmp = dfs(p[i].second, dp);
			ans1 = max(tmp, ans1);
			vis[p[i].second][0] = tmp;
			vis[p[i].second][1] = 1;
		}
	}

	cout << ans1;
}


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

	solve();

	/*
	int t;
	cin >> t;
	while (t) {
		solve();
		cout << "\n";
		t--;
	}
	*/

}



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

int main(){
    long long n,s,dp[10][1001]={0};
    dp[0][0]=1;
    for(int i=0;i<101;i++)
        for(int j=8;j>=0;j--)
            for(int k=0;k+i<1001;k++)
                dp[j+1][k+i]+=dp[j][k];
    while(cin>>n>>s,n||s)
        cout<<dp[n][s]<<endl;
}

Measured memory_bytes: 1240
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T>& V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> >& Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T>& mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;}
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);}
/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

template<class Type>
Type solve(Type res = Type()){
    ll K,X; cin >> K >> X;
    vector<int> ans;

    for(int p = -100000; p <= 100000; p++){
        if(abs(p-X) < K) ans.emplace_back(p);
    }
    cout << ans << endl;
    return res;
}
int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    solve<ll>(0);
    // cout << fixed << setprecision(12) << solve<ll>() << endl;
    return 0;
}

Measured memory_bytes: 3676
#include<stdio.h>
int main(void){
  int n,m,a=0,b=0,i;
  scanf("%d%d",&n,&m);
  for(i=n-1;i>=1;i--){
    a+=i;
  }
  for(i=m-1;i>=1;i--){
    b+=i;
  }
  
  if(n==1&&m==1){
    printf("0");
    return 0;
  }
  printf("%d",a+b);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const ll INF = 1000000000000000000LL;

ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

ll factorial(ll n) {
  ll answer = 1;
  while (n > 1) {
    answer *= n;
    answer %= mod;
    n--;
  }
  return answer;
}

ll combination(ll n, ll r) {
  return factorial(n) / (factorial(r) * factorial(n - r));
}

ll permutation(ll n, ll r) { return factorial(n) / factorial(n - r); }

template <typename T>
void remove(std::vector<T>& vector, unsigned int index) {
  vector.erase(vector.begin() + index);
}

map<ll, ll> prime_factor(ll n) {
  map<ll, ll> ret;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}
// for (auto p : prime_factor(n)) {
//	while (p.second--) {
//		cout << p.first << endl;
//	}
//}

vector<ll> divisor(ll n) {
  vector<ll> ret;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

bool compare_by_b(pair<ll, ll> a, pair<ll, ll> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

vector<ll> Eratosthenes(const ll N) {
  bool is_prime[1000000 + 1];
  vector<ll> P;
  for (ll i = 0; i <= N; i++) {
    is_prime[i] = true;
  }
  for (ll i = 2; i <= N; i++) {
    if (is_prime[i]) {
      for (ll j = 2 * i; j <= N; j += i) {
        is_prime[j] = false;
      }
      P.emplace_back(i);
    }
  }
  return P;
}

typedef vector<int> ivec;
typedef vector<string> svec;
typedef vector<ll> lvec;

int main() {
  int n;
  cin >> n;
  ivec p(n);
  REP(i, n) { cin >> p[i]; }
  int ans = 0;
  FOR(i, 1, n - 1) {
    int p1 = p[i - 1];
    int p2 = p[i];
    int p3 = p[i + 1];
    ivec ps = {p1, p2, p3};
    sort(ALL(ps));
    if (ps[1] == p2) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T> &p){ cout << "[" << p.first << ", " << p.second << "]"; return os; }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) vc<vc<T>> xs(n, vc<T>(m)); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define Return(expr) { Cout(expr); return 0; }
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

// constexpr int MOD = 1e9+7;

int main(void){
    Cin(int, n, k);
    Cins(int, n, a);
    Sort(a);
    ll ans = 0;
    For(i, n-k) ans += a[i];
    Cout(ans);
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int maxn = 105, oo = 1e9+7;
char grid[maxn][maxn];
int dp[maxn][maxn], indegree[maxn][maxn];
int h, w;

void dfs(int i, int j) {
	if(i == 0 && j == 0) {
		if(grid[i][j] == '#') dp[i][j] = 1;
		else dp[i][j] = 0;
	} else {
		int best_dp = oo;

		if(i-1 >= 0) {
			if(grid[i-1][j] == '.' && grid[i][j] == '#') {
				best_dp = min(best_dp, dp[i-1][j]+1);	
			} else {
				best_dp = min(best_dp, dp[i-1][j]);
			}
		}

		if(j-1 >= 0) {
			if(grid[i][j-1] == '.' && grid[i][j] == '#') {
				best_dp = min(best_dp, dp[i][j-1]+1);
			} else {
				best_dp = min(best_dp, dp[i][j-1]);
			}
		}

		dp[i][j] = best_dp;
	}

	if(i+1 < h) {
		indegree[i+1][j]--;
		if(indegree[i+1][j] == 0) {
			dfs(i+1, j);
		}
	}
	if(j+1 < w) {
		indegree[i][j+1]--;
		if(indegree[i][j+1] == 0) {
			dfs(i, j+1);
		}
	}
}

int main() {
	scanf("%d%d\n",&h,&w);

	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) {
			indegree[i][j] = 0;
			if(j > 0) indegree[i][j]++;
			if(i > 0) indegree[i][j]++;
			dp[i][j] = -1;
			scanf("%c", &grid[i][j]);
		}
		scanf("\n");
	}
	
	dfs(0, 0);
	printf("%d\n",dp[h-1][w-1]);
  return 0;
}


Measured memory_bytes: 384
#pragma GCC optimize ("-O3")
#include <bits/stdc++.h>  
#include <complex>
#include <queue>
#include <set>
#include <unordered_set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <fstream>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<int> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
ll MOD = 1e9+7;
#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(ll i = s; i < e; i++)
#define rforn(i,s) for(ll i = s; i >= 0; i--)
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 1e18
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define vvv64 vector<vv32>
#define vvvv64 vector<vvv32> 
// #define vvvvb64 vector<vector<vector<vector<bool> > > >
int maxi = 80 * 160 +10;
void solve()
{
	int h,w;
	cin>>h>>w;
	// vvvv64d p(h+1,vvv64(w+1,vv64(2*maxi+10,v64(2,0))));	
	vvv64 dp(h+1,vv64(w+1,v32(2*maxi+10,0)));	

	vector<vp64> arr(h+1,vp64(w+1));
	for (int i=1; i<=h;i++)
	{
		for (int j=1;  j<=w; j++)
			cin>>arr[i][j].fi;
	}
	for (int i=1; i<=h; i++)
	{
		for (int j=1; j<=w; j++)
			cin>>arr[i][j].se;
	}
	// dp[0][0][0][0]=1;
	// dp[0][0][0][1]=1;
	int zero=maxi;
	dp[0][1][zero]=1;
	dp[1][0][zero]=1;
	for (int i=1; i<=h; i++)
	{
		for (int j=1; j<=w; j++)
		{
			for (int k=0; k<2*maxi; k++)
			{
				// int diff1=arr[i][j].fi-arr[i][j].se;
				// int b=k+diff1;
				// if (b<0)
				// {
				// 	if (dp[i-1][j][abs(b)][0] || dp[i][j-1][abs(b)][0])
				// 		dp[i][j][k][0]=1;
				// }
				// else
				// {
				// 	if (dp[i-1][j][abs(b)][1] || dp[i][j-1][abs(b)][0])
				// 		dp[i][j][k][0]=1;
				// }

				// b=k-diff1;
				// if (b<0)
				// {
				// 	if (dp[i-1][j][abs(b)][0] || dp[i][j-1][abs(b)][0])
				// 		dp[i][j][k][0]=1;
				// }
				// else
				// {
				// 	if (dp[i-1][j][abs(b)][1] || dp[i][j-1][abs(b)][0])
				// 		dp[i][j][k][0]=1;
				// }
				int diff=arr[i][j].fi-arr[i][j].se;
				int val=k+diff;
				// if (i==1 && j==1)
				// 	cout<<val<<endl;
				if ( (val< 2*maxi && val>0) && (dp[i-1][j][val] || dp[i][j-1][val]))
					dp[i][j][k]=1;
				val=k-diff;
				if ( (val< 2*maxi && val>0) && (dp[i-1][j][val] || dp[i][j-1][val]))
					dp[i][j][k]=1;
			}
		}
	}
	// cout<<dp[1][1][2+zero]<<endl;
	int ans=1e9;
	for (int i=0; i<2*maxi; i++)
	{
		if (dp[h][w][i])
			ans=min(ans,abs(i-zero));
	}
	cout<<ans<<endl;
}
int32_t main()
{
    fast_cin();
    int t;
    t=1;
    while (t--)
    {
    	solve();
    }
    return 0;
} 

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


int main() {
	int N;
	int64_t a = 1000;
	int64_t b = 0;
	cin >> N;
	vector<int>kabu(N);
	for(int i=0;i<N;i++){
		cin >> kabu.at(i);
	}
	for(int i=0;i<N-1;i++){
		if(kabu.at(i)<kabu.at(i+1)){
			
			int64_t c = a/kabu.at(i);
			b += c;
			a -= kabu.at(i)*c;
		}
		else if(kabu.at(i)>kabu.at(i+1)){
			
			a += kabu.at(i)*b;
			b = 0;
		}
	}
	a += kabu.at(N-1)*b;
	cout << a << endl;

}





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

double P[100], T[100], V[100];
double ncr[55][55];
int main(){
	ncr[0][0] = 1.0;
	for(int i = 0 ; i < 50 ; i++)
		for(int j = 0 ; j < 50 ; j++)
			ncr[i+1][j] += ncr[i][j],
			ncr[i+1][j+1] += ncr[i][j];
	
	int N,M,L;
	cin >> N >> M >> L;
	for(int i = 0 ; i < N ; i++){
		cin >> P[i] >> T[i] >> V[i];
		P[i] /= 100.0;
		//P[i] = 1 - P[i];
	}
	for(int i = 0 ; i < N ; i++){
		double sum2 = 0;
		for(int l = 0 ; l <= M ; l++){
			double myTime = L / V[i] + l * T[i];
			double prob1 = ncr[M][l] * pow(P[i],l) * pow(1-P[i],M-l);
			//cout << i << " " << l << " " << prob1 << endl;
			double OKProb = 1.0;
			for(int j = 0 ; j < N ; j++){
				if( i == j ) continue;
				double sum = 0;
				for(int k = 0 ; k <= M ; k++){
					double time = L / V[j] + k * T[j];
					double prob2 = ncr[M][k] * pow(P[j],k) * pow(1-P[j],M-k);
					if( time > myTime + 1e-10 ){
						sum += prob2;
					}
				}
				OKProb *= sum;
			}
			sum2 += OKProb * prob1;
		}
		printf("%.10lf\n",sum2);
	}
}

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

typedef struct _Vector{
	int x,y;
}Vector;

int main(){
	Vector s1,s2;
	
	int q,x0,x1,x2,x3,y0,y1,y2,y3,i;
	
	for(cin>>q,i=q;i--;){
		
		cin>>x0>>y0>>x1>>y1>>x2>>y2>>x3>>y3;
		
		s1.x = x1-x0;
		s1.y = y1-y0;
		
		s2.x = x3-x2;
		s2.y = y3-y2;
		
		if(s1.x*s2.y - s1.y*s2.x == 0)cout<<2;
		else if(s1.x*s2.x + s1.y*s2.y == 0)cout<<1;
		else cout<<0;
		
		cout<<endl;
	}
}

Measured memory_bytes: 1164
#include<iostream>
using namespace std;
void call(int n) {
    int i = 1;
    for(i;i <= n;i++){
        if (i%3 == 0||i%10==3||i/10%10==3||i/100%10==3||i/1000%10==3) {
            cout << " " << i;
        }
   }
    cout<<endl;
}

int main(){
    int n;
    cin>>n;
    call(n);
    return 0;
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1234;
int x[maxn], f[maxn];
vector<int> to[maxn];
void cant(){
	cout << "IMPOSSIBLE" << endl;
	exit(0);
}
void calc(int u){
	if(to[u].size()){
		vector<int> cf(x[u] + 1, 1<<30);
		cf[0] = 0;
		for(int v : to[u]){
			calc(v);
			vector<int> nf(x[u] + 1, 1<<30);
			for(int i = 0; i <= x[u]; i++){
				if(cf[i] != (1<<30)){
					if(i + x[v] <= x[u]) nf[i + x[v]] = min(nf[i + x[v]], cf[i] + f[v]);
					if(i + f[v] <= x[u]) nf[i + f[v]] = min(nf[i + f[v]], cf[i] + x[v]);
				}
			}
			cf = nf;
		}
		f[u] = 1<<30;
		for(int i = 0; i <= x[u]; i++) f[u] = min(f[u], cf[i]);
		if(f[u] == (1<<30)) cant();
	} else {
		f[u] = 0;
	}
}
int main(){
	int n; cin >> n;
	for(int i = 2; i <= n; i++){
		int x; cin >> x;
		to[x].push_back(i);
	}
	for(int i = 1; i <= n; i++) cin >> x[i];
	calc(1);
	cout << "POSSIBLE" << endl;
	return 0;
}



Measured memory_bytes: 5756
import java.io.IOException;
import java.io.PrintStream;
import java.util.Scanner;

class Main
{
    public static void main(String[] args) throws IOException

    {
        Scanner in = new Scanner(System.in);
        P78BSolver s = new P78BSolver(in, System.out);
        s.read();
        s.solve();
    }
}

class P78BSolver
{
    Scanner in;
    PrintStream out;
    int X, Y, Z;

    public P78BSolver(Scanner s, PrintStream p)
    {
        in = s;
        out = p;
    }

    public void read() throws IOException
    {
        X = in.nextInt();
        Y = in.nextInt();
        Z = in.nextInt();
    }

    public void solve()
    {
        X -= Y + 2 * Z;
        System.out.println(1 + (X / (Y + Z)));
    }
}


Measured memory_bytes: 23764
#include <cstdio>
#include <climits>
#include <vector>

int w[100][100];
std::vector<int> mst;
std::vector<int> others;
typedef std::vector<int>::iterator itr;

int minimum(){
    if(others.size()<=0)return 0;
    int candiW=INT_MAX;
    itr candiI;
    for(itr i=mst.begin();i!=mst.end();i++){
        for(itr j=others.begin();j!=others.end();j++){
            if(w[*i][*j]<candiW){
                candiW = w[*i][*j];
                candiI = j;
            }
        }
    }
    mst.push_back(*candiI);
    others.erase(candiI);
    return candiW + minimum();
}

int main(){
    int i, j, n;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            scanf("%d",&w[i][j]);
            if(w[i][j]==-1)w[i][j]=INT_MAX;
        }
    }
    mst.push_back(0);
    for(i=1;i<n;i++)others.push_back(i);
    printf("%d\n",minimum());
    return 0;
}



Measured memory_bytes: 2776
#include <iostream>
#include <string>

int main() {
    int H, W;

    while (std::cin >> H >> W, H || W) {
        std::cout << std::string(W, '#') << std::endl;
        for (int i = 1; i < H - 1; ++i) {
            std::cout << "#" << std::string(W - 2, '.') << "#" << std::endl;
        }
        std::cout << std::string(W, '#') << std::endl;
        std::cout << std::endl;
    }
}


Measured memory_bytes: 3096