akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

static const ll MOD = 1000000007LL;



ll fib(ll a, ll b){
  if(b <= 0) return 1;
  ll x = 1;
  ll y = 1;
  rep(i,b){
    ll z = x + y;
    x = y;
    y = z;
  }
  return y;
}

ll solve(int start, int H, int W, int goal){
  vector<vector<ll>> dp(H+1, vector<ll>(W, 0));
  dp[0][start] = 1;
  rep(i,H){
    rep(j,W){
      if(j-1>=0){
        ll a = j-2;
        ll b = W-1 - (j+1);
        ll p = dp[i][j];
        p *= fib(2, a);
        p %= MOD;
        p *= fib(2, b);
        p %= MOD;
        dp[i+1][j-1] += p;
        dp[i+1][j-1] %= MOD;
      }
      {
        ll a = j-1;
        ll b = W-1 - (j+1);
        ll p = dp[i][j];
        p *= fib(2, a);
        p %= MOD;
        p *= fib(2, b);
        p %= MOD;
        dp[i+1][j] += p;
        dp[i+1][j] %= MOD;
      }
      if(j+1<W){
        ll a = j-1;
        ll b = W-1 - (j+2);
        ll p = dp[i][j];
        p *= fib(2, a);
        p %= MOD;
        p *= fib(2, b);
        p %= MOD;
        dp[i+1][j+1] += p;
        dp[i+1][j+1] %= MOD;
      }
    }
  }
  return dp[H][goal];
}


int main(){
  int H, W, K;
  cin >> H >> W >> K;

  cout << solve(0,H,W,K-1) << endl;
  
  return 0;
}


Measured memory_bytes: 256
// 2011/03/04 Tazoe

#include <iostream>
using namespace std;

struct wall{
	int x;
	int y;
	int r;
};

bool saf_jdg(struct wall wal, int x1, int y1, int x2, int y2)
{
	if((x1-wal.x)*(x1-wal.x)+(y1-wal.y)*(y1-wal.y)<wal.r*wal.r
	 &&(x2-wal.x)*(x2-wal.x)+(y2-wal.y)*(y2-wal.y)<wal.r*wal.r)
		return false;

	int vx = x2-x1;
	int vy = y2-y1;
	int cx = wal.x-x1;
	int cy = wal.y-y1;

	int vc = vx*cx+vy*cy;

	int v2 = vx*vx+vy*vy;
	int c2 = cx*cx+cy*cy;
	int r2 = wal.r*wal.r;

	if(vc<0)
		if(c2<r2)
			return true;
		else
			return false;

	if(vc>v2){
		int dx = wal.x-x2;
		int dy = wal.y-y2;
		int d2 = dx*dx+dy*dy;
		if(d2<r2)
			return true;
		else
			return false;
	}

	if(c2*v2-vc*vc<=r2*v2)
		return true;
	else
		return false;
}

int main()
{
	while(true){
		int n;
		cin >> n;
		if(n==0)
			break;

		struct wall wal[100];
		for(int i=0; i<n; i++)
			cin >> wal[i].x >> wal[i].y >> wal[i].r;

		int m;
		cin >> m;

		for(int i=0; i<m; i++){
			int tx, ty, sx, sy;
			cin >> tx >> ty >> sx >> sy;

			bool saf_flg = false;
			for(int j=0; j<n; j++)
				if(saf_jdg(wal[j], tx, ty, sx, sy)){
					saf_flg = true;
					break;
				}

			if(saf_flg)
				cout << "Safe" << endl;
			else
				cout << "Danger" << endl;
		}
	}

	return 0;
}

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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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

int H, W;

int a[500][500];
vector<tuple<int, int, int, int>> op;


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

    for(int i = 0; i < 500; i++){
        for(int j = 0; j < 500; j++){
            a[i][j] = -1;
        }
    }

    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> a[i][j];
        }
    }

    for(int i = 0; i < H; i++){
        if(i % 2 == 0){
            for(int j = 0; j < W; j++){
                if(a[i][j] % 2 == 1){
                    if(j < W-1){
                        a[i][j+1] += 1;
                        op.push_back(make_tuple(i, j, i, j+1));
                    }else{
                        if(i < H-1){
                            a[i+1][j] += 1;
                            op.push_back(make_tuple(i, j, i+1, j));
                        }
                    }
                }
            }
        }else{
            for(int j = W-1; j >= 0; j--){
                if(a[i][j] % 2 == 1){
                    if(j > 0){
                        a[i][j-1] += 1;
                        op.push_back(make_tuple(i, j, i, j-1));
                    }else{
                        if(i < H-1){
                            a[i+1][j] += 1;
                            op.push_back(make_tuple(i, j, i+1, j));
                        }
                    }
                }
            }
        }
    }

    cout << op.size() << endl;
    for(int i = 0; i < op.size(); i++){
        cout << get<0>(op[i])+1 << ' ' << get<1>(op[i])+1 << ' ' << get<2>(op[i])+1 << ' ' << get<3>(op[i])+1 << endl; 
    }

    return 0;
}


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

int main() {
    string S;
    cin >>S;
    for(int i=0;i<3;i++){
        if(S.at(i)=='1')S.at(i)='9';
        else S.at(i)='1';
    }
    cout <<S<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){

  char matriz[3][4];

  for (int i = 0; i < 3; ++i){
    scanf("%s", matriz[i]);
  }

  for (int i = 0; i < 3; i++){
    for (int j = 0; j < 3; ++j){
      if (j == i)
        printf("%c", matriz[i][j]);
    }
  }

  printf("\n");

  return 0;
}


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

typedef long long int ll;
typedef long double ld;

#define Pb push_back
#define Mp make_pair

#define ff first
#define ss second

#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))

#define INF LONG_LONG_MAX
#define MINF LONG_LONG_MIN

#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define db1(x) cout<<#x<<" : "<<x<<endl;
#define db2(x,y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<endl;
#define db3(x,y,z) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\t"<<#z<<" : "<<z<<endl;

void solve()
{
  ll n,W;
  cin >> n >> W;
  ll w[n],v[n];
  for(ll i=0;i<n;i++)
  {
    cin >> w[i] >> v[i];
  }
  ll dp[n+1][W+1];
  memset(dp,0,sizeof(dp));
  for(int i=0;i<=n;i++)
  {
    for(int j=0;j<=W;j++)
    {
      if(i==0 || j==0)  dp[i][j] = 0;
      else if(w[i-1] <= j)
      {
        dp[i][j] = max(v[i-1] + dp[i-1][j-w[i-1]],dp[i-1][j]);
      }
      else
      {
        dp[i][j] = dp[i-1][j];
      }
    }
  }
  cout << dp[n][W];
}

signed main()
{
  IOS;
  //freopen("input.txt", "rt", stdin);
  //freopen("output.txt", "wt", stdout);
  int t=1;
  //cin >> t;
  while(t--)
  {
    solve();
  }
  return 0;
}
/*==============================================================================================================================================================*/


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

using namespace std;

using ll = long long;

constexpr char newl = '\n';

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

    for (int i = 0; i < 5; i++) {
        int x;
        cin >> x;
        if (x == 0) {
            cout << i + 1 << newl;
            break;
        }
    }

    return 0;
}

Measured memory_bytes: 3668
#include<bits/stdc++.h>
using namespace std;
#define int long
using pi=pair<int,int>;
signed main(){
    int n, k, s = 0;
    cin >> n >> k;
    vector<int> h(n);
    for (auto& i : h) cin >> i;
    sort(h.begin(), h.end());
    for (int i = 0; i < n - k; ++i) s += h[i];
    cout << s;
    
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <string.h>

using namespace std;

int main(void)
{
    string S, a, b;
    int i, n;

    cin >> S;

    n = S.size();

    while(n>=1){
        i = n/2;
        a = S.substr(0, i);
        b = S.substr(i, i);

        if(a == b && n != S.size()){
            cout << i*2 << endl;
            break;
        }
        n--;
    }

    return 0;
}

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

int main(void) {
    double x1, x2, y1, y2, r;

    scanf("%lf %lf %lf %lf", &x1, &x2, &y1, &y2);
    r = sqrt((y1-x1)*(y1-x1)+(y2-x2)*(y2-x2));
    printf("%.4f\n", r);
    return 0;
}



Measured memory_bytes: 2048
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, price[100], len, x = 6, f[100010];
int main(){
	scanf("%d", &n);
	price[++len] = 1;
	while(x <= n){
		price[++len] = x;
		x *= 6;
	}
	x = 9;
	while(x <= n){
		price[++len] = x;
		x *= 9;
	}
	memset(f, 63, sizeof(f));
	f[0] = 0;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= len; ++j){
			if(i >= price[j]) f[i] = min(f[i], f[i - price[j]] + 1);
		}
	}
	printf("%d\n", f[n]);
	return 0;
}

Measured memory_bytes: 1152
while 1:
    n = float(input())
    if n<0:break
    m=n-int(n)
    a=bin(int(n))[2:].zfill(8)+'.'
    for _ in range(4):
        m*=2
        if m>=1:
            a+='1'
            m-=1
        else: a+='0'
    print('NA' if m>1e-10 or 13<len(a) else a)

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

int main(){
  int a[3][3];
  rep(i,3) {
    rep(j,3) cin >> a[i][j];
  }
  vector<bool> f(101,false);
  int n;
  cin >> n;
  rep(i,n) {
    int b;
    cin >> b;
    f[b] = true;
  }
  bool ans = false;
  rep(i,3) {
    bool u = true;
    rep(j,3) {
      if(!f[a[i][j]]) u = false;
    }
    if(u) ans = true;
  }
  rep(i,3) {
    bool u = true;
    rep(j,3) {
      if(!f[a[j][i]]) u = false;
    }
    if(u) ans = true;
  }
  if(f[a[0][0]] && f[a[1][1]] && f[a[2][2]]) ans = true;
  if(f[a[0][2]] && f[a[1][1]] && f[a[2][0]]) ans = true;
  cout << (ans? "Yes" : "No") << endl;
  return 0;
}


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

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

  int x;
  cin >> x;
  if (x == 3 || x == 5 || x == 7) {
    cout << "YES\n";
  } else {
    cout << "NO\n";
  }
}


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

int main(){
    int n,m;
    cin>>n>>m;
    if(n+m>0)cout<<1<<endl;
    if(n+m==0)cout<<0<<endl;
    if(n+m<0)cout<<-1<<endl;
    return 0;
}


Measured memory_bytes: 3072
#include <iostream>
using namespace std;
char a[102][102];
 
void dfs(int  m,int n,char o){
  if(a[m][n]!=o){
    return ;
  }
  a[m][n]=0;
  dfs(m+1,n,o);
  dfs(m,n+1,o);
  dfs(m-1,n,o);
  dfs(m,n-1,o);
}
int main(){
  while(1){
    int b,c;
    cin >> b >> c;
    if(b==0 && c==0)
      break;
    for(int i=1;i<=b;i++){
      for(int j=1;j<=c;j++){
    cin >> a[i][j];
      }
    }
    int d=0;
    for(int i=1;i<=b;i++){
      for(int j=1;j<=c;j++){
    if(a[i][j]!=0){
      d++;
      dfs(i,j,a[i][j]);
    }
      }
    }
    cout << d << endl;
  }
  return 0;
}

Measured memory_bytes: 1476
from collections import deque
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
friend = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
check = [0]*n
union = [-1]*n
union[0] = 0
for i in range(n):
    if check[i]: continue
    que = deque([i])
    while que:
        u = que.popleft()
        for v in friend[u]:
            if check[v]: continue
            union[v] = i
            check[v] = 1
            que.append(v)
            
brock = [[] for _ in range(n)]
for _ in range(k):
    c, d = map(int, input().split())
    if union[c-1] == union[d-1]:
        brock[c-1].append(d-1)
        brock[d-1].append(c-1)
        
ans = [0]*n
check = [0]*n
for i in range(n):
    if check[i] or union[i]==-1: continue
    que = deque([i])
    for j in range(i+1, n):
        if union[j] == union[i]: que.append(j)
    res = len(que)
    while que:
        u = que.popleft()
        check[u] = 1
        ans[u] = res-len(friend[u])-len(brock[u])-1
print(*ans)

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

const int N=1e5+1e3;

long long a[N];

int n,k;

long long ans=9223372036854775807;

long long minn(long long a,long long b){
	if(a<b) return a;
	return b;
}

int num;

int main(){
//	freopen("c.out","r",stdin);
//	freopen("a.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		if(a[i]>=0&&num==0) {
			num=i;
		}
	}
	if(num==0){
			ans=minn(ans,-a[n-k+1]);
	}
	for(int i=1;i<num;i++){
		if(i+k-1>n) break;
		if(a[i+k-1]<0){
			ans=minn(ans,-a[i]);
		}
		else{
			ans=minn(ans,a[i+k-1]-a[i]*2);
			ans=minn(ans,a[i+k-1]*2-a[i]);
		}
		if(a[i+k-1]==0){
			ans=minn(ans,-a[i]);
		} 
	}
	for(int i=num;i<=n-k+1;i++){
		if(num==0) break;
		ans=minn(ans,a[i+k-1]);
	}
	printf("%lld",ans);
	return 0; 
} 

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
using ll = long long;

int main() {
  const long double pi = 3.1415926535;
  long double R;
  std::cin >> R;
  std::cout << std::fixed << std::setprecision(10) <<(2 * R * pi) << std::endl;
  return 0;
}


Measured memory_bytes: 3780
import * as fs from "fs";

const input = (fs.readFileSync("/dev/stdin", "utf8") as string).split("\n");
//const n = +input[0];
//const a = [];
//for(let i=0;i<n;i++){
//	a.push(input[i+1].split(" ").map((x:string):number=>+x));
//}

//const [n, m] = input[0].split(" ").map((x: string): number => +x);
//const a = input[1].split(" ").map((x: string): number => +x);

function compareFunc(a, b){
    return a-b;
}

const n: number = +input[0];

console.log(n*n*n);

Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
const long long MOD = 1000000007;

map<int, int> prime;

void prime_fuctor(int N)
{
    for (int i = 2; i * i <= N; i++) {
        while (N % i == 0) {
            prime[i]++;
            N /= i;
        }
    }
    if (N != 1) prime[N]++;
}

int main()
{
    ll N, ans = 1;
    cin >> N;
    repd(i, 2, N + 1) prime_fuctor(i);

    for (auto itr = prime.begin(); itr != prime.end(); itr++) {
        if (ans == 0) ans = itr->second+ 1;
        else ans *= itr->second + 1;
        ans %= MOD;
    }

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

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

using namespace std;

int n,len,q;
int long num;
int block;
int a[100010];
int b[100010];
int to[100010];
int next[100010];
int step[100010];

int find(int x)
{
	int ans=0;
	int l=x+1;
	int r=n;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(a[mid]-a[x]<=len)
		{
			l=mid+1;
			ans=mid;
		}
		else
		{
			r=mid-1;
		}
	}
	return ans;
}

void build(void)
{
	for(int i=1;i<n;i++)
	{
		to[i]=find(i);
	}
	to[n]=n+1;
	block=sqrt(n);
	num=ceil(n/block);
	for(int i=1;i<=n;i++)
	{
		b[i]=(i-1)/block+1;
	}
	for(int i=1;i<=n;i++)
	{
		int p=i;
		int cnt=0;
		while(b[p]==b[i])
		{
			p=to[p];
			cnt++;
		}
		next[i]=p;
		step[i]=cnt;
	}
}

int query(int x,int y)
{
	int res=0;
	while(b[x]<b[y])
	{
		res+=step[x];
		x=next[x];
	}
	while(x<y)
	{
		x=to[x];
		res++;
	}
	return res;
}

int main(void)
{
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	sort(a+1,a+n+1);
	cin >> len >> q;
	build();
	for(int i=1;i<=q;i++)
	{
		int x,y;
		cin >> x >> y;
		if(x>y)
		{
			swap(x,y);
		}
		cout << query(x,y) << endl;
	}
	return 0;
}

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

int main(){
  int n;
  cin >> n;
  
  // スタート座標 この値を動かしていく
  vector<int> position(2, 0);
  
  int t = 0;
  for (int i=0; i<n; i++){
    int tmp_t;
    vector<int> tmp_position(2);
    cin >> tmp_t >> tmp_position.at(0) >> tmp_position.at(1);
    
    // tまでに移動可能かどうかを判断
    while(t!=tmp_t){
      t++;
      
      // xを値に合わせる->yを値に合わせる->反復していく
      if (position.at(0)>tmp_position.at(0)){
        position.at(0)--;
      } else if (position.at(0)<tmp_position.at(0)){
        position.at(0)++;
      } else { // x座標が一致する場合->y座標をいじる
        if (position.at(1) > tmp_position.at(1)){
          position.at(1)--;
        } else if (position.at(1) < tmp_position.at(1)){
          position.at(1)++;
        } else { // y座標が一致するときは+1する
          position.at(1)++;
        }
      }
    }
    if(position==tmp_position){
      continue;
    } else {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
  
}

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

    int n, m;
    cin >> n >> m;

    if(n == 1 && m == 2){
        cout << 3;
        return 0;
    }
        if(n == 1 && m == 3){
        cout << 2;
        return 0;
    }

    if(n == 2 && m == 1){
        cout << 3;
        return 0;
    }

    if(n == 2 && m == 3){
        cout << 1;
        return 0;
    }

    if(n == 3 && m == 2){
        cout << 1;
        return 0;
    }

    if(n == 3 && m == 1){
        cout << 2;
        return 0;
    }


    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int nextInt();
char compare(int x, int y);
int med3(int x, int y, int z);
void quickSort(int *a, int left, int right);
void sort(int *a, int size);

int N, i;
int A[100000], B[100000], C[100000];
long long int a, b;

int main(){
	N=nextInt();
	for(i=0; i<N; i++){
		A[i]=nextInt();
		B[i]=nextInt();
		C[i] = A[i] + B[i];
		b += B[i];
	}
	sort(C, N);
	for(i=0; i<N; i+=2){
		a += C[i];
	}
	printf("%lld\n", a-b);
	return 0;
}

int nextInt(){
	int f=0; char c=getchar();
	while((c<'0')||('9'<c)){c=getchar();}
	while((c>='0')&&(c<='9')){f=f*10+(c-'0'); c=getchar();}
	return f;
}

char compare(int x, int y){
	return x > y;
}

int med3(int x, int y, int z){
	if(compare(x, y)){
		if (compare(y, z)){return y;}else if(compare(z, x)){return x;}else{return z;}
	} else {
		if (compare(z, y)){return y;}else if(compare(x, z)){return x;}else{return z;}
	}
}

void quickSort(int *a, int left, int right){
	if(left >= right){return;}
	int pivot = med3(a[left], a[left+(right-left)/2], a[right]);
	int l=left, r=right;
	int t;
	while(1){
		while (compare(a[l], pivot)){l++;}
		while (compare(pivot, a[r])){r--;}
		if(l>=r){break;}
		t=a[l]; a[l]=a[r]; a[r]=t;
		l++; r--;
	}
	quickSort(a, left, l-1);
	quickSort(a, r+1, right);
}

void sort(int *a, int size){
	quickSort(a, 0, size-1);
}


Measured memory_bytes: 1280
n=input()
p=list(map(int,input().split()))
def func(i,j):
    if i == len(p) :
        return "YES"
    elif p[i]==i+1 :
        return func(i+1,j)
    elif p[p[i]-1]==i+1 and j<2 :
        j+=1
        return func(i+1,j)
    else :
        return "NO"
print(func(0,0))


Measured memory_bytes: 3060
from math import *
N,M=map(int,input().split())
d1,d2=[],[]
for n in range(1,int(sqrt(M))+1):
    if M%n == 0:
        d1.append(n)
        d2.append(M//n)
divs=d2+d1[::-1]
for d in divs:
    if d*N <= M:
        print(d)
        break

Measured memory_bytes: 38640
/*

Coded by peyha X

*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int NMAX=1e5+1,INF=1e9+1;
int n,k,hauteurs[NMAX],dp[NMAX];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> k;
	
	for(int i=1;i<=n;i++){
		cin >> hauteurs[i];
	}
	dp[0]=INF;
	for(int i=2;i<=n;i++){
		int best=INF;
		
		for(int j=1;j<=k;j++){
			if(i-j>=1){
				best=min(best,dp[i-j]+abs(hauteurs[i]-hauteurs[i-j]) );
			}
		}
		dp[i]=best;
	}
	
	cout << dp[n] << '\n';

	
	
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <numeric>
#include <limits>
#include <cmath>
#include <iomanip>
#include <sstream>
 
#define ALL(a)  (a).begin(),(a).end()
 
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

ll gcd(ll a, ll b) {
    if (a < b) return gcd(b, a);
    return b ? gcd(b, a % b) : a;
}

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

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

    ll n; cin >> n;
    string s; cin >> s;

    ll r = 0, g = 0, b = 0;
    ll ans = 0;

    for (ll i = 0; i < n; i++) {
        if (s[i] == 'R') r++;
        if (s[i] == 'G') g++;
        if (s[i] == 'B') b++;
    }

    for (ll i = 0; i < n; i++) {
        for (ll j = i+1; j < n; j++) {
            if (s[i] != s[j]) {
                // if (s[i] != 'R' && s[j] != 'R') {
                //     ans += r;
                //     if (s[2*j - i] == 'R') ans--;
                // }
                // if (s[i] != 'G' && s[j] != 'G') {
                //     ans += g;
                //     if (s[2*j - i] == 'G') ans--;
                // }
                if (s[i] != 'B' && s[j] != 'B') {
                    ans += b;
                    if (2*j - i < n) {
                        if (s[2*j - i] == 'B') ans--;
                    }
                    if (2*i - j >= 0) {
                        if (s[2*i - j] == 'B') ans--;
                    }
                    if ((i+j) % 2 == 0) {
                        if (s[(i+j) / 2] == 'B') ans--;
                    }
                }
            }
        }
    }

    cout << ans << endl;
    
}

Measured memory_bytes: 3668
#include <bits/stdc++.h>
using namespace std;
inline void read (int &x) {
    char ch = getchar(); int f = 0; x = 0;
    while (!isdigit(ch)) { if (ch == '-') f = 1; ch = getchar(); }
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar(); if (f) x = -x;
} const int N = 2e5 + 10;
char ch[N]; int len;
signed main() {
    scanf ("%s", ch + 1);
    len = strlen (ch + 1);
    for (int i = 1; i <= len; ++i) {
        ch[i] == '?' ? putchar ('D') : putchar (ch[i]);
    } return puts (""), 0;
}


Measured memory_bytes: 3848
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus >= 201703L
#        pragma GCC target("avx2")
#    else
#        pragma GCC target("avx")
#    endif

#endif
// 実数の場合
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

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

    vector<int> a(3);
    cin >> a[0] >> a[1] >> a[2];

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

    cout << a[0] + a[1] << endl;

    return 0;
}


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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//==================================

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif

    int N;
    cin >> N;
    unordered_set<char> s;
    for (int i = 0; i < N; i++) {
        char c;
        cin >> c;
        s.emplace(c);
    }

    cout << (s.size() == 3 ? "Three\n" : "Four\n");

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
const ll mod = 1000000007;
ll x[2000000];
int main() {
  ll N, H, W;
  cin >> N >> H >> W;
  for(int i = 0; i < N; i++) {
    ll y;
    cin >> y;
    ll l = i * W;
    if(i % 2 == 0) l += y;
    else l -= y;
    x[l]++;
    x[l+W]--;
  }
  for(int i = 1; i < N * W; i++) {
    x[i] += x[i-1];
  }
  ll ans = 0;
  for(int i = 0; i < N * W; i++) {
    if(x[i] == 0) ans++;
  }
  cout << ans * H << endl;
  return 0;
}



Measured memory_bytes: 3164
#include <stdio.h>
#define INF 1 << 30

int H,W;
int white = 0;
int visited[50][50];

int vx[4] = {0,1,0,-1};
int vy[4] = {1,0,-1,0};

int que[3000];
int top = 0;
int bottom = 0;

void push(int x){
  que[bottom] = x;
  bottom++;
}

int pop(){
  if(top >= bottom) return -1;
  return que[top++];
}

int main(void){
  scanf("%d%d",&H,&W);

  char str[W];
  for(int i = 0;i < H;i++){
    scanf("%s",str);
    for(int j = 0;j < W;j++){
      if(str[j] == '#'){
        visited[i][j] = -1;
      }else{
        visited[i][j] = 0;
        white++;
      }
    }
  }
  push(0);
  visited[0][0] = 1;

  while(1){
    int p = pop();
    if(p == -1) break;

    int x = p/1000;
    int y = p%1000;

    for(int i = 0;i < 4;i++){
      int xx = x+vx[i];
      int yy = y+vy[i];
      if(0 <= xx && xx < H && 0 <= yy && yy < W){
        if(visited[xx][yy] == 0){
          push(xx*1000+yy);
          visited[xx][yy] = visited[x][y]+1;
        }
      }
    }
  }

  if(!visited[H-1][W-1]) printf("-1\n");
  else printf("%d\n",white-visited[H-1][W-1]);

  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<map>
using namespace std;
typedef long long int ll;
vector<ll>dat;
vector<ll>res;
ll m(ll i,ll j){
    if(res[i]!=-1)return res[i];
    if(i>=dat.size()-1){
        return 0;
    }
    res[i]=1e9;
    for(ll k=1;k<=j&&i+k<dat.size();k++){
        res[i]=min(res[i],abs(dat[i]-dat[i+k])+m(i+k,j));
    }
    return res[i];
}
int main(){
    ll a,aux,k;
    cin>>a>>k;
    for(ll i=0;i<a;i++){
        cin>>aux;
        dat.push_back(aux);
    }
    res=vector<ll> (a,-1);
    cout<<m(0,k)<<endl;
    return 0;
}


Measured memory_bytes: 11128
a,b=map(int,input().split())
c=[]
for _ in range(b):
    c.append(list(map(int,input().split())))

for i in range(b):
    for j in range(i):
        if c[i][0]==c[j][0] and c[i][1]!=c[j][1]:
            print(-1)
            exit()
for i in range(b):
    if a==b==1:
        break
    if c[i][1]==0 and c[i][0]==1:
        print(-1)
        exit()

result=[0]*a
for i in range(b):
    result[c[i][0]-1]=c[i][1]

if result[0]==0 and a>=2:
    result[0]=1

for i in range(a):
    result[i]=str(result[i])

print(''.join(result))

Measured memory_bytes: 9172
import java.util.*;

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

		int ans = Integer.parseInt(sc.next());

		for (int i=0; i<n-1; i++){
			ans = gcd(ans, Integer.parseInt(sc.next()));
		}
		System.out.println(ans);
	}

	public static int gcd(int num1, int num2) {
		if (num2 == 0){
			return num1;
		}else {
			return gcd(num2, num1%num2);
		}
	}
}

Measured memory_bytes: 47228
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
typedef long long ll;
typedef double dd;
#define For(i,j,k) for (int i=j;i<=k;++i)
#define Forr(i,j,k) for (int i=j;i>=k;--i)
#define Set(a,p) memset(a,p,sizeof(a))
using namespace std;

template<typename T>bool chkmax(T& a,T b) {return a<b?a=b,1:0;}
template<typename T>bool chkmin(T& a,T b) {return a>b?a=b,1:0;}

ll a,b,c,x,y,ans=1e15;

inline void file() {
	freopen("C.in","r",stdin);
	freopen("C.out","w",stdout);
}

int main() {
//	file();
	scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&x,&y);
	ll z=min(x,y); c*=2;
	chkmin(ans,a*x+b*y);
	chkmin(ans,a*(x-z)+b*(y-z)+c*z);
	chkmin(ans,c*max(x,y));
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <sstream>
using namespace std;

#define REP(i,a,n) for(i=a; i<n; i++)
#define rep(i,n) REP(i,0,n)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define foreach(it,x) for(typeof(x.begin()) it=x.begin(); it!=x.end(); it++)

// 500 <= n <= 5000, n+=100
int main(){
    int n,a,b;

    while( cin >> n, n ){
        int ret = 999999999;
        for(a=0; 200*a <= n; a++){
            for(b=0; 200*a + 300*b <= n; b++){
                if( (n - (200*a + 300*b)) % 500 != 0 ) continue;
                int c = (n - (200*a + 300*b)) / 500;
                int ac = 1520*(a/5) + 380*(a%5);
                int bc = 1870*(b/4) + 550*(b%4);
                int cc = 2244*(c/3) + 850*(c%3);
                //printf("a=%d, b=%d, c=%d, sum=%d,  n=%d, ac=%10.4lf, bc=%10.4lf, cc=%10.4lf, sum=%lf\n",a,b,c,200*a+300*b+500*c,n,ac,bc,cc,ac+bc+cc);
                ret = min(ret, ac + bc + cc);
            }
        }
        printf("%d\n",(int)(ret));
    }
    return 0;
}

Measured memory_bytes: 0
#include <iostream>

using namespace std;

int main() {
  char S[4];
  int price = 700;

  cin >> S;
  for (int i = 0; i < 4; ++i) {
    if (S[i] == 'o') {
      price += 100;
    }
  }

  cout << price;

  return 0;
}


Measured memory_bytes: 256
s[61][61],q[99];
main(x,y,i,j,f,g,_x,_y){
	for(;scanf("%d%d",&x,&y),x;){
		memset(s,0xff,sizeof(s));
		for(j=1;j<2*y;j++)
			for(i=1;i<2*x;i++)
				s[i][j]=0;
		for(j=1;j<2*y;j++)
			for(i=(j&1)?2:1;i<2*x;i+=2)scanf("%d",s[i]+j);
		q[0]=0x10001;s[1][1]=1;f=0;g=1;
		for(;f!=g;){
			_x=q[f]>>16,_y=q[f]&0xffff;f=(f+1)%99;
			if(s[_x][_y-1]==0&&s[_x][_y-2]==0)q[g]=((_x)<<16)|(_y-2),g=(g+1)%99,s[_x][_y-2]=s[_x][_y]+1;
			if(s[_x][_y+1]==0&&s[_x][_y+2]==0)q[g]=((_x)<<16)|(_y+2),g=(g+1)%99,s[_x][_y+2]=s[_x][_y]+1;
			if(s[_x-1][_y]==0&&s[_x-2][_y]==0)q[g]=((_x-2)<<16)|(_y),g=(g+1)%99,s[_x-2][_y]=s[_x][_y]+1;
			if(s[_x+1][_y]==0&&s[_x+2][_y]==0)q[g]=((_x+2)<<16)|(_y),g=(g+1)%99,s[_x+2][_y]=s[_x][_y]+1;
			if(s[2*x-1][2*y-1])break;
		}
		printf("%d\n",s[2*x-1][2*y-1]);
	}
	exit(0);
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
const int mod=1e9+7;
const int INF =LONG_LONG_MAX;
inline int gcd(int a,int b){if(a==0) return b;return gcd(b%a,a);}
inline int pow(int a,int n,int mod){if(n==0)return 1;int p=pow(a,n/2,mod);p=(p%mod*p%mod)%mod;if(n%2) return (p%mod*a%mod)%mod;else return p;}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s1,s2;
    cin>>s1>>s2;
    int m=s1.length();
    int n=s2.length();
    int dp[m+1][n+1];
    for(int i=0;i<=m;i++)
    {
        for(int j=0;j<=n;j++)
        {  dp[i][j]=0;
            if(i==0||j==0){dp[i][j]=0;continue;}
            if(s1[i-1]==s2[j-1])dp[i][j]=1+dp[i-1][j-1];
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }

  /*  for(int i=0;i<=m;i++)
    {
        for(int j=0;j<=n;j++)
        {
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }*/
  int i=m,j=n;
  vector<char>ans;
  while(i>0&&j>0)
  {
    if(s1[i-1]==s2[j-1]){ans.push_back(s1[i-1]);i--;j--;}
    else
    {
        if(dp[i-1][j]>=dp[i][j-1])i--;
        else j--;
    }
  }
for(int i=ans.size()-1;i>=0;i--)
    cout<<ans[i];
 return 0;
}


Measured memory_bytes: 70656
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << "\n";
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

void chmax(ll &x, ll y) {
    if (x < y) x = y;
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int R, C, K;
    cin >> R >> C >> K;

    vector<vll> v(R + 1, vll(C + 1, 0));
    REP(i, K) {
        int r, c; ll vv;
        cin >> r >> c >> vv;
        --r; --c;
        v[r][c] = vv;
    }

    vector<vector<vll>> dp(R + 1, vector<vll>(C + 1, vll(4, 0)));

    REP(i, R) REP(j, C) {
        REP(k, 4) {
            chmax(dp[i + 1][j][k], dp[i][j][k]);
            chmax(dp[i][j + 1][k], dp[i][j][k]);
        }
        if (v[i][j] > 0) {
            REP(k, 3) {
                chmax(dp[i][j + 1][k + 1], dp[i][j][k] + v[i][j]);
            }

            REP(k, 3) {
                chmax(dp[i + 1][j][0], dp[i][j][k] + v[i][j]);
            }
        }
    }

    REP(i, 4) {
        chmax(dp[R][C][i], dp[R-1][C][i]);
        chmax(dp[R][C][i], dp[R][C-1][i]);
    }

    print(*max_element(ALL(dp[R][C])));

}


Measured memory_bytes: 706512
from collections import deque
import copy

h,w=map(int,input().split())
Inf=float('inf')
maze1=[]
for _ in range(h):
  s=list(input())
  for u in range(w):
    if s[u]=='.':
      s[u]=Inf
  maze1.append(s)
  
def maze_solve(maze,sy,sx):
  qu=deque([[sy,sx]])
  maze[sy][sx]=0
  
  while qu:
    y,x=qu.popleft()
    
    T=maze[y][x]
    for i in ([1,0],[-1,0],[0,1],[0,-1]):
      ny=y+i[0]
      nx=x+i[1]
      if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
        
        if maze[ny][nx]>T+1:
          maze[ny][nx]=T+1
          qu.append([ny,nx])
          
  ans=-Inf
  for i in range(h):
    for j in range(w):
      if maze[i][j]!='#' and maze[i][j]!=Inf:
        ans=max(ans,maze[i][j])
  return ans
  

ans=-Inf
for i in range(h):
  for j in range(w):
    if maze1[i][j]!='#':
      maze2=copy.deepcopy(maze1)
      ans=max(ans,maze_solve(maze2,i,j))
            
            
print(ans)

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

int main() {
  int X, Y;
  cin >> X >> Y;

  for (int i = 0; i <= X; i++) {
    int y = X - i;
    if ((i * 2 + y * 4) == Y) {
      cout << "Yes" << endl;
      return 0;
    }
  }

  cout << "No" << endl;
}

Measured memory_bytes: 3636
use std::io::*;
use std::str::FromStr;

#[allow(unused_macros)]
macro_rules! scan {
  ($e:expr; $t:ty) => {
    $e.get::<$t>()
  };
  ($e:expr; $($t:ty), *) => {
    ($($e.get::<$t>(),)*)
  };
  ($e:expr => $i:expr; $t:ty) => {
    (0..$i).map(|_| $e.get::<$t>()).collect::<Vec<$t>>()
  };
  ($e:expr => $row:expr, $col:expr; $t:ty) => {
    (0..$i).map(|_| scan!($e => $col; $t)).collect::<Vec<$t>>()
  }
}

struct Scanner<R: Read> {
  reader: R
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
  fn new(reader: R) -> Scanner<R> {
    Scanner { reader: reader }
  }
  fn safe_get<T: FromStr>(&mut self) -> Option<T> {
    let token = self.reader.by_ref().bytes().map(|c| c.unwrap() as char)
      .skip_while(|c| c.is_whitespace())
      .take_while(|c| !c.is_whitespace())
      .collect::<String>();
    if token.is_empty() { None } else { token.parse().ok() }
  }
  fn get<T: FromStr>(&mut self) -> T {
    if let Some(v) = self.safe_get() { v } else {
      writeln!(stderr(), "Terminated with EOF").unwrap();
      std::process::exit(0);
    }
  }
}

fn merge(vec: &mut Vec<i32>, left: usize, mid: usize, right: usize) -> i64 {
  let n1 = mid - left;
  let n2 = right - mid;
  let mut l = Vec::with_capacity(n1 + 1);
  let mut r = Vec::with_capacity(n2 + 1);
  for i in 0..n1 {
    l.push(vec[left + i]);
  }
  for i in 0..n2 {
    r.push(vec[mid + i]);
  }
  l.push(std::i32::MAX);
  r.push(std::i32::MAX);
  let mut ans = 0;
  let (mut i, mut j) = (0, 0);
  for k in left..right {
    if l[i] <= r[j] {
      vec[k] = l[i];
      i += 1;
    }
    else {
      vec[k] = r[j];
      j += 1;
      ans += l.len() - 1 - i;
    }
  }
  ans as i64
}

fn merge_sort(vec: &mut Vec<i32>, left: usize, right: usize) -> i64 {
  let mut ans = 0;
  if left + 1 < right {
    let mid = (left + right) / 2;
    ans += merge_sort(vec, left, mid);
    ans += merge_sort(vec, mid, right);
    ans += merge(vec, left, mid, right);
  }
  ans
}

fn main() {
  let cin = stdin();
  let cin = cin.lock();
  let mut sc = Scanner::new(cin);
  let n = scan!(sc; usize);
  let mut a = scan!(sc => n; i32);
  println!("{}", merge_sort(&mut a, 0, n))
}



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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};


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

  ll x;
  cin >> x;

  ll amari = x%100;
  ll n = x/100;

  ll buy = amari/5;
  if(amari%5 != 0)
    buy++;

  if(n >= buy)
    cout << 1 << endl;
  else
    cout << 0 << endl;

}


Measured memory_bytes: 256
def resolve():
    import math
    from functools import reduce
    
    def lcm_base(x, y):
        return (x * y) // math.gcd(x, y)
      
    def lcm_list(numbers):
        return reduce(lcm_base, numbers, 1)
    
    n = int(input())
    A = list(map(int, input().split()))
    lcm = lcm_list(A)
    m = lcm-1
    ans = 0
    for i in range(n):
      ans += m % A[i]
    print(ans)
resolve()

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

#define int long long
using ll = long long;
using ull = unsigned long long;
#define repi(n) for (long long i = 0; i < (n); ++i)
#define repj(n) for (long long j = 0; j < (n); ++j)
#define repk(n) for (long long k = 0; k < (n); ++k)
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define itr(itr) for (auto&& v : (itr))
#define updatemax(t, v) ((t) = std::max<decltype(t)>((t), (v)))
#define updatemin(t, v) ((t) = std::min<decltype(t)>((t), (v)))

int nextp[5000], inWhichLoop[5000];
ll score[5000];
vector<vector<ll>> loops;
signed main() {
  int n;
  ll k;
  cin >> n >> k;
  repi(n) cin >> nextp[i];
  repi(n)-- nextp[i];
  repi(n) cin >> score[i];
  repi(n) inWhichLoop[i] = -1;
  repi(n) {
    if (inWhichLoop[i] >= 0) continue;
    int loopIndex = loops.size();
    int current = i;
    vector<ll> newLoop;
    while (inWhichLoop[current] < 0) {
      inWhichLoop[current] = loopIndex;
      newLoop.push_back(score[current]);
      current = nextp[current];
    }
    loops.push_back(newLoop);
  }
  ll result = LLONG_MIN;
  for (auto&& loop : loops) {
    int looplen = loop.size();
    vector<ll> sum(looplen * 3 + 1);
    sum[0] = 0;
    repi(looplen * 3) sum[i + 1] = sum[i] + loop[i % looplen];
    auto k0 = k;
    ll result0 = 0;
    bool allowzero = false;
    if (sum[looplen] > 0 && k0 / looplen >= 2) {
      result0 = sum[looplen] * (k0 / looplen - 1);
      k0 = k0 % looplen + looplen;
      allowzero = true;
    }
    ll result1 = allowzero ? 0 : LLONG_MIN;
    repi(looplen) rep(j, 1, min(k0, looplen * 2) + 1) updatemax(result1, sum[i + j] - sum[i]);
    updatemax(result, result0 + result1);
  }
  cout << result << endl;
}


Measured memory_bytes: 3848
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit
#include <cstdio>	// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>	// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()
#define X first
#define Y second.first
#define Z second.second
#define DEBUG 1
 
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> POS;

char cord[3];

int main()
{
//	cut here before submit 
//	freopen ("testcase.cwh10", "r", stdin );
	int n, h;
	while (scanf ("%d %d", &n, &h ) && n && h ){
		set<POS> pos;
		pos.clear(); 
		rep (i, h ){
			int u, v;
			scanf ("%s %d %d", cord, &u, &v );
			u--, v--;
			if (cord[0] == 'x' && cord[1] == 'z' ) swap (cord[0], cord[1] );
			switch (cord[0] ) {
				case 'x':
					pos.insert (POS (u, P(v, -1 ) ) );
					break;
				case 'y':
					pos.insert (POS (-1, P(u, v ) ) );
					break;
				case 'z':
					pos.insert (POS (u, P (-1, v ) ) );
					break;
			} // end switch
		} // end rep
		int res = n*n*n;
		set<POS>::iterator it,jt;
		for (it = pos.begin(); it != pos.end(); it++ ){
			if ((*it).X == -1 ){					
				res -= n;
			} // end if
		} // end rep

		map<POS,int> intersect;
		intersect.clear();
		for (it = pos.begin(); it != pos.end(); it++ ){
			if ((*it).Y == -1 ){
				int cx = (*it).X;
				int cz = (*it).Z;
				res -= n;
				for (jt = pos.begin(); jt != pos.end(); jt++ ){
					if ((*jt).X == -1 && (*jt).Z == cz ){
						POS is; is.X = cx, is.Y = (*jt).Y, is.Z = cz;
					  	intersect[is]++;
					} // end if
				} // end rep
			} // end if
		} // end rep

		for (it = pos.begin(); it != pos.end(); it++ ){
			if ((*it).Z == -1 ){
				int cx = (*it).X;
				int cy = (*it).Y;
				res -= n;
				for (jt = pos.begin(); jt != pos.end(); jt++ ){
					if ((*jt).X == -1 && (*jt).Y == cy ){
						POS t; t.X = cx, t.Y = cy, t.Z = (*jt).Z;
					  	intersect[t]++;
					} // end if
				} // end rep
				for (jt = pos.begin(); jt != pos.end(); jt++ ){
					if ((*jt).Y == -1 && (*jt).X == cx ){
						POS t; t.X = cx, t.Y = cy, t.Z  = (*jt).Z;
					  	intersect[t]++;
					} // end if
				} // end rep
			} // end if
		} // end rep

		map<POS,int>::iterator ii = intersect.begin();
		for (; ii != intersect.end(); ii++ ){
			if ((*ii).second == 3 ) res += 2;
			else
				res += (*ii).second;
		} // end for
		printf ("%d\n", res );
	} // end while

	return 0;
}

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

int main(){
  int N,M;
  cin >> N >> M;
  vector<int> cnt(M,0);
  for(int i=0;i<N;++i){
    int K; cin >> K ;
    for(int j=0;j<K;++j){
      int A; cin >> A; --A;
      ++cnt[A];
    }
  }
  int ans =0;
  for(int i=0;i<M;i++){
    if(cnt[i] == N){
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
H, W = map(int, input().split())
a = [[0] * W for _ in range(H)]

for h in range(H):
    a[h] = [inp for inp in input()]
#print(a)
check = [[0] * W for _ in range(H)]

for h in range(H):
    for w in range(W):
        if a[h][w] == '#':
	        check[h][w] = 1
#print(a)
#print(check)
final_w = [0] * W
for h in range(H):
    final_w = [final_w[w] + check[h][w] for w in range(W)]
    
final_h = [0] * H
for w in range(W):
    final_h = [final_h[h] + check[h][w] for h in range(H)]
  
#print(final)
for h in range(H):
    res = ''
    for w in range(W):
        if final_w[w] >= 1 and final_h[h] >= 1:
            res += a[h][w]
    print(res + '\n')


Measured memory_bytes: 3188
//  RAKSHIT KADAM
 #include <bits/stdc++.h>

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree< int ,  null_type ,  less<int> ,  rb_tree_tag ,  tree_order_statistics_node_update>
 #warning !!!check the size of arrayss!!!

 #define ll long long
 #define int long long
 #define MOD  1000000007
 #define newMOD  998244353
 #define MAX 200006
 #define Need_for_speed(activated) ios_base :: sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
 #define satisfy ll t; cin>> t; while(t--)
 #define inp(n) int n;cin >> n
 #define mp make_pair
 #define pb push_back
 #define fore(i,a,b) for(ll i=a;i<b;i++)
 #define endl "\n"
 #define x first
 #define y second
 #define forci(i,n) for(ll i=0;i<n;i++)
 #define INF 1000000000000000005
 #define vi vector<ll>
 #define PI 3.14159265

using namespace std;
//int power(int x, unsigned int y, unsigned int m){ if (y == 0) return 1;int p = power(x, y/2, m) % m;  p = (p * p) % m;                                                  return (y%2 == 0)? p : (x * p) % m;}

//ll modInverse(int a, int m){int g = gcd(a, m); { return power(a, m-2, m);}}
//ll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);}
ll a[MAX];
void solve()
{
    
    string a,d;
    a="2";
    cin>>d;
    a+=d;
    if(a[3]==a[4]&& a[5]==a[6])cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
signed main()
{
    Need_for_speed(activated);
//       satisfy
//       {
//           solve();
//       }
//
  solve();
//
    
    return 0;}




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

freq_w = [ 0 for _ in range(W)]
freq_h = [ 0 for _ in range(H)]
pos = dict()

for _ in range(M):
    h, w = map(int, input().split())
    freq_h[h-1] += 1
    freq_w[w-1] += 1
    pos[(h-1, w-1)] = True


m_w = max(freq_w)
pos_w = [i for i, j in enumerate(freq_w) if j == m_w]

m_h = max(freq_h)
pos_h = [i for i, j in enumerate(freq_h) if j == m_h]

max_ = m_w + m_h - 1
found = False
#
# for el in pos:
#     i, j = el
#     max_

for i in pos_h:
    for j in pos_w:
        if not((i, j) in pos):
            found = True
            break
    if found == True:
        break

print(max_ + int(found))


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

int main(){
    int n,m;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int a,b;
        cin >> a >> b;
        a--; b--;
        if(min(abs(n/2-a), abs((n-1)/2-a)) < min(abs(n/2-b), abs((n-1)/2-b))){
            int c = min(b, n-1-b);
            cout << c%3 +1 << endl;
        }else{
            int c = min(a, n-1-a);
            cout << c%3 +1 << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3096
from heapq import*
import sys
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S],H=0,[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   if c+f<F[v]:F[v]=c+f;heappush(H,(F[v],v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r();p=map(int,f[2:].split())
  if'0'==f[0]:print(g(n,E,*p))
  else:c,d,e=p;E[c]+=[(e,d)];E[d]+=[(e,c)]
for e in iter(r,'0 0\n'):s(*map(int,e.split()))


Measured memory_bytes: 6304
X, K, D = map(int, input().split())
if X < 0:
    X = -1 * X

if K * D <= X:
    print(X - K * D)
else:
    n = X // D
    if X % D > 0:
        n += 1
    if (K - n) % 2 == 0:
        print(-1 * (X - n * D))
    else:
        print(X - n * D + D)

Measured memory_bytes: 61700
#include<stdio.h>
int main(){
	int N,i,r=1,s=0,A[101];
	scanf("%d",&N);
	for(i=1;i<=N;i++)scanf("%d",&A[i]);
	for(i=1;i<=N;i++){
		while(A[i]==1 && i<=N){
			r++;
			i++;
		}
		if(s<r || s==0)s=r;
		r=1;
	}
	printf("%d\n",s);
	return 0;
}



Measured memory_bytes: 2104
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        try(Scanner sc = new Scanner(System.in)){
        	while(sc.hasNext()) {
        		
        		int a  = 0;
        		String str = sc.next();
        		
        		for(int i=0;i<4;i++) {
        			char b = str.charAt(i);
        			if(b=='+')
        				a++;
        			if(b=='-')
        				a--;
        		}
        		System.out.println(a);
        		
        	}
        }
    }
}


Measured memory_bytes: 21972