akhauriyash/Code-Regression huggingface dataset:
/**
 *    author:  math2do
 *    created: 04.09.2020 14:47:25 IST
**/

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector <int> arr(n);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  } 
  
  const int pinf = numeric_limits<int>::max();
  vector <int> dp(n, pinf);
  dp[0] = 0;
  for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j <= min(i + k, n - 1); j++) {
      int cost = abs(arr[i] - arr[j]);
      dp[j] = min(dp[j], dp[i] + cost);
    } 
  } 
  cout << dp[n - 1] << endl;
  return 0;
}


Measured memory_bytes: 3984
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
#define REP(i, n) for (int i=0; i<(int)(n); ++i)
 
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;}

// ll a[100010][3];
// ll dp[110][100010];  // [品物][重さ] としたときの価値の最大値
// ll weight[110], value[110];
const ll LINF = 1LL<<60;

const int MAX_N = 110;
const int MAX_W = 1e9;
const int MAX_VAL = 100100;

ll N, W;
ll v[MAX_N], w[MAX_N];

// dp[x][y] x時点で価値がy以上となるようにした重さの最小値
ll dp[MAX_N][MAX_VAL];

int main(){
  cin >> N >> W;
  REP(i, N){
    cin >> w[i] >> v[i];
  }
  REP(i, MAX_N){
    REP(j, MAX_VAL){
      dp[i][j] = LINF;
    } 
  } 
  dp[0][0]=0;

  // dpテーブル更新
  for(int i=0; i<N; i++){
    for(ll value=0; value<MAX_VAL; value++){
      if(value - v[i] >= 0){
        chmin(dp[i+1][value], dp[i][value-v[i]] + w[i]);
      }
      chmin(dp[i+1][value], dp[i][value]);
    }
  }
  ll res = 0;
  for(ll sum=0; sum<MAX_VAL; sum++){
    if(dp[N][sum] <= W) res = sum;
  }
  cout << res << endl;
}

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

string s[3];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	for(int i=0;i<3;i++){
		cin>>s[i];
	}
	for(int i=0;i<3;i++){
		cout<<s[i][i];
	}
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int a,b,c,d;

int main() {
  INCANT;
  cin >> a >> b >> c >> d;
  
  string ans = c>a?"1":"0";
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
 
public class Main {
	public void exec() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        while(true) {
        	int n = Integer.parseInt(br.readLine());
        	if(n==0) break;
        	int[] sary = new int[n];
        	double avg=0, var=0;
        	int i=0;
        	for(String s: br.readLine().split(" ")) {
        		avg += sary[i++] = Integer.parseInt(s);
        	}
        	avg /= n;
        	for(int s: sary) {
        		var += Math.pow(s - avg,2);
        	}
        	out.printf("%.4f\n",Math.sqrt(var/n));
        }
        out.flush();
    }
  
    public static void main(String[] args) throws IOException {
        new Main().exec();
    }
}

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

int main()
{
    int n, t, a;
    cin >> n >> t >> a;
    vector<int> h(n);
    for(int i = 0; i < n; ++i) cin >> h[i];

    for(int i = 0; i < n; ++i)
    {
        h[i] = 1000 * t - (h[i] * 6);
    }
    int min = 1e9, pos = -1;
    for (int i = 0; i < n; ++i)
    {
        if (min > abs(h[i] - a * 1000))
        {
            min = abs(h[i] - a * 1000);
            pos = i + 1;
        }
    }

    cout << pos << endl;
}

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

using namespace std;

const int P = 998244353;

const int N = 5e5+5;

int f[N];
int finv[N];

int nk[N];
int mk[N];

int n,m;

int qpow(int a, int b)
{
	int res = 1;
	while(b)
	{
		if(b%2)
			res = res*a %P;
		
		a = a*a %P;
		b /= 2; 
	}
	return res;
}

int getInv(int a)
{	
	return qpow(a,P-2);
}

void init()
{
	f[0] = 1;
	
	int t = max(n,m);
	
	for(int i = 1; i <= t; i++)
	{
		f[i] = (f[i-1]*i)%P;
	}
	finv[t] = getInv(f[t]) % P;

	for(int i = t; i > 0; i--)
	{
		finv[i-1] = finv[i]*i %P;
	}
	
	nk[0] = 1, mk[0] = 1;
	for(int i = 1; i <= t; i++)
	{
		nk[i] = nk[i-1]*(n+1) % P;
		mk[i] = mk[i-1]*(m+1) % P;
	}
}

int choose(int a, int b)
{
	int A = f[a]*finv[b] % P;
	int B = A*finv[a-b] % P;
	
	int res = B;

	return res; 
}

long long ans;

int cal(int k)
{
//	int res = (( (nk[m-k]*mk[n-k])%P * f[k])%P *(choose(n,k)*choose(m,k))%P) % P;
	
	int res;
	int A = nk[m-k]*mk[n-k]%P;
	int B = A*f[k] %P;
	int C = B*choose(n,k) %P;
	int D = C*choose(m,k) %P;
	res = D;
	
	if(k%2)
	{
		return -res;
	}
	else
	{
		return res;
	}
}

void debug()
{
	for(int i = 0; i <= max(n,m); i++)
	{
		printf("f[%lld]=%lld\n",i,f[i]);
	}
}

signed main()
{
	cin >> n >> m;
	
	init();
//	debug();
	
	for(int i = 0; i <= min(n,m); i++)
	{
		ans += cal(i);
		ans = (ans+P) %P;
//		printf("res[%lld]=%lld\n", i, cal(i));
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 15872
#!/usr/bin/env python3
(n,m,),*b=[[*map(int,i.split())]for i in open(0)]
b=sorted(b,key=lambda x:x[1])
p=0
c=0
for i in b:
    if i[0]>=p:
        c+=1
        p=i[1]
print(c)


Measured memory_bytes: 92420
import java.lang.reflect.Array;
import java.util.*;

/**
 * Created by Santa.
 */
public class Main {

  static int N;
  static int K;
  static long Q;
  static int A;
  static int B;
  static long C;
  static double min = 9999999;
  static long ans = 0;


  static class pair implements Comparable{
          public long a;
          public long b;

          pair(){
              this.a = 0;
              this.b = 0;
          }

    @Override
    public int compareTo(Object o) {

            if(((pair)o).a > this.a)return -1;
        if(((pair)o).a < this.a)return 1;

      return 0;
    }

    pair(long a, long b){
              this.a = a;
              this.b = b;
          }

          public void set(long a, long b) {
              this.a = a;
              this.b = b;
          }
      }



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

    int N = scanner.nextInt();
    int M = scanner.nextInt();


    pair[] map = new pair[N];

    for (int i = 0; i < N; i++) {

        long tempa = scanner.nextLong();
        long tempb = scanner.nextLong();
        map[i] = new pair(tempa, tempb);

    }

    Arrays.sort(map);

    int cnt = 0;
    long ans = 0;

      for (int i = 0; i < N; i++) {
//          System.out.println(map[i].a);
//          if(cnt >= M)break;

//          System.out.println(ans + " " + cnt);
          if(cnt + map[i].b >= M){
//              cnt = M;
              ans += map[i].a * (M - cnt);
              break;
          }else{
              cnt += map[i].b;
              ans += map[i].a * map[i].b;
          }

//          if(cnt >= M)break;

      }


      System.out.println(ans);

//    System.out.println(getAns());





  }

//  static public int getAns(){
//    Scanner scanner = new Scanner(System.in);
//
//    int w = scanner.nextInt();
//
//
//
//
//    return (H - h) * (W - w);
//  }

}


Measured memory_bytes: 90664
#include<bits/stdc++.h>
using namespace std;
const int N=100000;

int main ()
{
string a[100000];
int n,m,i;
cin>>n>>m;
for (i=1;i<=n;i++)
cin >> a[i];
for (i=0;i<=m+1;i++)
{
	cout << "#";
}
cout << endl;
for (i=1;i<=n;i++)
{
cout <<"#"<<a[i]<<"#";
cout << endl;
}
for (i=0;i<=m+1;i++)
{
	cout << "#";
}
return 0;
}




Measured memory_bytes: 1024
#include <iostream>

int n;
long long h, w, a[1010], b[1010];
int main() {
	std::cin >> n >> h >> w;
	for (int i = 0; i < n; ++i)
		std::cin >> a[i] >> b[i];

	long long ans = 0;
	for (int i = 0; i < n; ++i)
		if (a[i] >= h && b[i] >= w)
			++ans;

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


Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in  = new Scanner(System.in);
        int k = in.nextInt();
        long ans = 0;
        for(int i=1;i<=k;++i){
            for(int j=1;j<=k;++j){
                for(int l=1;l<=k;++l){
                    int a = gcd(i,j);
                    int b  = gcd(a,l);
                    ans+=b;
                }
            }
        }
        System.out.println(ans);
    }
    public static int gcd(int a,int b){
        if(a==0)return b;
        return gcd(b%a,a);
    }
}


Measured memory_bytes: 35808
#include <iostream>
using namespace std;
int main(){
    double w,h,x,y;
    cin >> w >> h >> x >> y;
    cout << w*h/2.000000 << endl;
    if (2*x==w&&2*y==h)
        cout << 1 << endl;
    else
        cout << 0 << endl;
    return 0;
}


Measured memory_bytes: 256
function abs() {
    echo $(($1>0?$1:-$1))
}

read N
read T A

function temper() {
    local h=$1
    echo $((T * 1000 - 6 * h))
}
function temper_diff() {
    local h=$1
    echo $(abs $(($(temper $h) - $A * 1000)))
}

heights=(`cat`)
ans=0
min=`temper_diff ${heights[0]}`
end=${#heights[@]}
for((i=1;i<end;++i))
do
    t=`temper_diff ${heights[i]}`
    if ((min > t))
    then
        ans=$i
        min=$t
    fi
done
echo $((ans + 1))


Measured memory_bytes: 1120
# include <iostream>

int main(){
  int a,b;
  std::cin >> a >> b;

  if( a < b ) std::cout << "a < b" << std::endl;
  if( a == b) std::cout << "a == b" << std::endl;
  if( a > b) std::cout << "a > b" << std::endl;

  return 0;
}

Measured memory_bytes: 3080
import math

a,b,n=list(map(int,input().split()))

# for i in reversed(range(b)):
#     if i<=n:
#         print(math.floor(a*i/b))
#         break

if b <= n:
    print(math.floor(a*(b-1)/b))
else:
    print(math.floor(a*n/b))

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

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

using ll = long long;
using lb = long double;
using P = pair<ll,ll>;
using graph = vector<vector<ll>>;
using V = vector<ll>;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const ll INF = 1LL<<60;
const ll mod = 1000000007LL;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
ll hcnt[300005],wcnt[300005];

int main() {
  ll N;
  cin>>N;
  vector<lb> t(N),v(N);
  rep(i,N) cin>>t[i];
  rep(i,N) cin>>v[i];
  vector<lb> V(40005,INF);
  ll T = 0;
  ll cnt = 0;
  rep(i,N) cnt += t[i]*2;
  rep(i,cnt+1){
    chmin(V[i],(lb)i/2);
    chmin(V[cnt-i],(lb)i/2);
  }
  rep(i,N){
    for(int j = T; j < T+t[i]*2;j++){
      chmin(V[j],v[i]);
    }
    rep(j,T){
      chmin(V[T-j-1],v[i]+(lb)(j+1)/2);
    }
    for(int j = T+t[i]*2;j<cnt+1;j++){
      chmin(V[j],v[i]+(lb)(j-T-t[i]*2)/2);
    }
    T += 2*t[i];
  }
  lb ans = 0;
  for(int i = 1; i <= cnt; i++){
    ans += (lb)(V[i]+V[i-1])/4;
  }
  cout<<fixed<<setprecision(5);
  cout<<ans<<endl;
}

Measured memory_bytes: 4264
n, k = [ int(v) for v in input().split() ]
burgur = [ (0,0,0,1) ]
for _ in range(51):
    x, y, z, w = burgur[-1]
    y = w + 1
    z = 2 * w + 2
    w = 2 * w + 3
    burgur.append((x,y,z,w))

def eat(level,position):
    left, middle, right, _length = burgur[level]
    if level == 0:
        return 1
    else:
        if position == left:
            return 0
        elif position == middle:
            return 2**level
        elif position == right:
            return 2**(level+1) - 1
        elif left< position < middle:
            return eat(level-1, position-1)
        elif middle< position < right:
            return 2**level + eat(level-1, position-middle-1)

print(eat(n,k-1))

Measured memory_bytes: 38384
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

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

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

    int n;
    cin>>n;
    vector<P> ps(n);
    rep(i, n) cin>>ps[i].first>>ps[i].second;
    sort(ps.begin(), ps.end());
    rep(i, n) cout<<ps[i].first<<' '<<ps[i].second<<endl;
}


Measured memory_bytes: 3596
N, M, C = map(int, input().split())
Bm = list(map(int, input().split()))
n = 1
ans = 0
while n <= N:
    An = list(map(int, input().split()))
    sum = 0
    for i in range(0, M):
        sum += An[i] * Bm[i]
    if sum + C > 0:
        ans += 1
    n += 1
print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef pair<int,int *> P;
typedef pair<long long,int>PP;
typedef long long ll;
int main(){
  int a,b,k;
  cin>>a>>b>>k;
  int mp[101];
  for(int i=0;i<101;i++){
    mp[i]=0;
  }
  for(int i=1;i<=a;i++){
    if(a%i==0){
      mp[i]=1;
    }
  }
  for(int i=1;i<=b;i++){
    if(b%i==0){
      mp[i]+=1;
    }
  }
  int ans=0;
  for(int i=100;i>=1;i--){
    if(mp[i]==2){
      ans++;;
      if(ans==k){
	cout<<i<<endl;
	return(0);
      }
    }
  }
  cout<<ans<<endl;
  return(0);
}


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

int main(){
  string s;
  int n;
  cin >> n;
  cin >> s;
  rep(i, s.size()){
    rep(j, n){
      if(s.at(i) == 'Z'){
        s.at(i) = 'A';
        continue;
      }
      s.at(i)++;
    }
  }
  std::cout << s << '\n';
  return 0;
}

Measured memory_bytes: 256
use proconio::{input, fastout};

#[fastout]
fn main() {
    input! {
        n: usize, y: usize,
    }

    for i in 0..std::cmp::min(y/10000, n)+1 {
        for j in 0..(n+1-i) {
            let k = n-i-j;
            let sum = i*10000 + j*5000 + k*1000;
            if y == sum {
                println!("{} {} {}", i,j,k);
                return;
            } else if y < sum { break; }
        }
    }
    println!("-1 -1 -1");
}

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

typedef long long ll;
typedef long double ld;

#define pb push_back
#define sort(s) sort(s.begin(),s.end())
#define reverse(s) reverse(s.begin(),s.end())
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)

const ll mod = 1e9+7;

//最大公約数
ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}

//最小公倍数
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

//素数判定
bool isPrime(ll x){
    ll i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

//桁和
int digsum(ll n) {
    int res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

//桁数
int dignum(ll n) {
    int res = 0;
    while(n > 0) {
        res++;
        n /= 10;
    }
    return res;
}

//文字列中の特定の文字カウント
ll stringcount(string s,char c){
    return count(s.cbegin(),s.cend(),c);
}

//階乗
ll ka(ll i){
    ll res=1;
    while(i>0){
        res=res*i;
        i--;
    }
    return res;
}
 
//ncr
ll ncr(ll x,ll y){
    ll a = x;
    ll b = 1;
    if(y>(x/2)){
        y=x-y;
    }
    for(ll i=1;i<y;i++){
        a*=x-i;
        b*=i+1;
    }
    return a/b;
}

//フィボナッチ数列
ll f(ll x){
    ll dp[x+1];
    dp[1]=1;
    dp[2]=1;
    for(ll i=3;i<=x;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[x];
}

//char->int
int ctoi(char c){
    return c-'0';
}



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

    for(int i=0;i<s.size();i++){
        if(s[i]==','){
            cout << " ";
        }else{
            cout << s[i] ;
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

string s;
int q;

int main(){
	cin>>s>>q;
	bool B=0;
	string t1="",t2="";
	for(int i=0;i<q;i++){
		int t;
		cin>>t;
		if(t==1) B^=1;
		else{
			char c;
			cin>>t>>c;
			if(t==1^B) t1+=c;
			else t2+=c;
		}
	}
	reverse(t1.begin(),t1.end());
	s=t1+s+t2;
	if(B) reverse(s.begin(),s.end());
	cout<<s<<endl;
}

Measured memory_bytes: 1348
#include <iostream>
using namespace std;
using ll = long long;

int main() {
	ll n, m, h[100000], a, b, good = 0, tenbo[100000] = { 0 };
	cin >> n >> m;
	for (int i = 0; i < n; i++) 
		cin >> h[i];

	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		if (h[a - 1] <= h[b - 1])
			tenbo[a - 1]++;
		if (h[b - 1] <= h[a - 1])
			tenbo[b - 1]++;
	}

	for (int i = 0; i < n; i++) {
		if (tenbo[i] == 0)
			good++;
	}
	
	cout << good << endl;
	return 0;
}

Measured memory_bytes: 5148
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1e9;
const LL LLINF = 1e16;

int main(){
    int n;
    cin >> n;
    vector<LL> b(n+1, INF);
    rep(i, n-1) cin >> b[i+1];
    LL ans = 0;
    rep(i, n) ans += min(b[i], b[i+1]);
    cout << ans << endl;
}

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

int H, W;

vector<pair<int,int> > bfs(const int grid[8][8])
{
  int dist[8][8];
  for (int i = 0; i < H; i++) {
    fill_n(dist[i], W, 0);
  }
  dist[0][0] = true;
  queue<pair<int,int> > q;
  q.push(make_pair(0, 0));
  const int color = grid[0][0];
  vector<pair<int,int> > ans;
  while (!q.empty()) {
    ans.push_back(q.front());
    const int i = q.front().first, j = q.front().second;
    q.pop();
    for (int d = 0; d < 4; d++) {
      static const int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};
      const int k = i + di[d], l = j + dj[d];
      if (0 <= k && k < H && 0 <= l && l < W && grid[k][l] == color && !dist[k][l]) {
        dist[k][l] = true;
        q.push(make_pair(k, l));
      }
    }
  }
  return ans;
}

int dfs(const int grid[8][8], int depth, int C)
{
  const vector<pair<int,int> > c = bfs(grid);
  if (depth == 0) {
    if (grid[0][0] == C) {
      return c.size();
    } else {
      return 0;
    }
  } else {
    int ans = 0;
    for (int i = 1; i <= 6; i++) {
      int g[8][8];
      for (int j = 0; j < H; j++) {
        copy(grid[j], grid[j]+W, g[j]);
      }
      for (vector<pair<int,int> >::const_iterator it = c.begin(); it != c.end(); ++it) {
        g[it->first][it->second] = i;
      }
      ans = max(ans, dfs(g, depth-1, C));
    }
    return ans;
  }
}

int main()
{
  int C;
  while (cin >> H >> W >> C && H != 0) {
    int grid[8][8];
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        cin >> grid[i][j];
      }
    }
    cout << dfs(grid, 5, C) << endl;
  }
  return 0;
}

Measured memory_bytes: 912
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>

using namespace std;


int main(void) {

	int H, W;

	while (cin >> H >> W, H, W) {
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				if (i == 0 || i == H - 1)
					cout << "#";
				else if (j == 0 || j == W - 1)
					cout << "#";
				else 
					cout << ".";
			}
			cout << endl;
		}
		cout << endl;
	}

	return 0;
}

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

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

  ll N, K; cin >> N >> K;
  vector<ll> A(N); for (ll i = 0; i < N; i++) cin >> A[i];
  vector<ll> A2 = A;

  for (ll i = 0; i < K; i++) {
    vector<ll> D(N + 1, 0);
    for (ll j = 0; j < N; j++) {
      ll l = j - A2[j];
      if (l < 0) l = 0;
      ll r = j + A2[j] + 1;
      if (r > N) r = N;
      D[l]++;
      D[r]--;
    }

    bool ok = true;
    A2[0] = D[0];
    if (A2[0] < N) ok = false;
    for (ll j = 1; j < N; j++) {
      A2[j] = A2[j - 1] + D[j];
      if (A2[j] < N) ok = false;
    }
    if (ok) {
      cout << N;
      for (ll j = 1; j < N; j++) {
        cout << " " << N;
      }
      return 0;
    }
  }

  cout << A2[0];
  for (ll j = 1; j < N; j++) {
    cout << " " << A2[j];
  }

  return 0;
}

Measured memory_bytes: 7948
#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 INF = 1e18;

struct ST {
  ll a, b;
};
bool operator==(const ST& x, const ST& y){
  return (x.a == y.a && x.b == y.b);
}

int N, M;
vector<pair<ll,ll>> G[100005];
vector<ST> states[100005];


int main(){
  cin >> N >> M;
  rep(i,M){
    ll a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    G[a].emplace_back(b,c);
    G[b].emplace_back(a,c);
  }

  queue<pair<int,ST>> que;
  que.push(make_pair(0,(ST){1,0}));
  while(!que.empty()){
    pair<int,ST> p = que.front(); que.pop();

    bool flg = false;
    rep(i,states[p.first].size()){
      if(states[p.first][i] == p.second) flg = true;
    }
    if(flg) continue;
    states[p.first].push_back(p.second);

    if(states[p.first].size() > 2){
      cout << 0 << endl;
      return 0;
    }

    rep(i,G[p.first].size()){
      pair<ll,ll> j = G[p.first][i];
      que.push(make_pair(j.first,(ST){-p.second.a,j.second-(p.second.b)}));
    }
  }

  ll lb = 0, ub = INF;
  rep(i,N){
    if(states[i].size() == 1){
      if(states[i][0].a > 0){
        //x+b>0
        lb = max(lb, -states[i][0].b);
      }else{
        //-x+b>0
        ub = min(ub, states[i][0].b);
      }
    }else{
      if(states[i][0].a > 0 && states[i][1].a < 0){
        //このノードのチェック
        //x+b>0
        lb = max(lb, -states[i][0].b);
        //-x+b>0
        ub = min(ub, states[i][1].b);

        //ノード0のチェック
        //x+a == -x+b <=> x = (b-a)/2 > 0
        if(llabs(states[i][1].b - states[i][0].b)%2 == 0){
          ll x = (states[i][1].b - states[i][0].b) / 2;
          lb = max(lb, x-1);
          ub = min(ub, x+1);
        }else{
          cout << 0 << endl;
          return 0;
        }
      }
      else if(states[i][0].a < 0 && states[i][1].a > 0){
        //このノードのチェック
        //-x+b>0
        ub = min(ub, states[i][0].b);
        //x+b>0
        lb = max(lb, -states[i][1].b);

        //ノード0のチェック
        //-x+a == x+b <=> x = (a-b)/2 > 0
        if(llabs(states[i][0].b - states[i][1].b)%2 == 0){
          ll x = (states[i][0].b - states[i][1].b) / 2;
          lb = max(lb, x-1);
          ub = min(ub, x+1);
        }else{
          cout << 0 << endl;
          return 0;
        }
      }
      else{
        cout << 0 << endl;
        return 0;
      }
    }
  }

  lb++;
  if(ub-lb <= 0) cout << 0 << endl;
  else cout << ub - lb << endl;

  return 0;
}


// ios::sync_with_stdio(false);


Measured memory_bytes: 18192
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

#include<bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=1e5+5;
const int mod=1e9+7;

int n,W,V,w[N],v[N],dp[N][105];
int rec(int val,int i){
    if(val==0) return 0;
    if(i>n or val<0) return 1e9;
    int &cache=dp[val][i];
    if(cache!=-1) return cache;
    rec(val-1,i);
    cache=rec(val,i+1);
    cache=min(cache,w[i]+rec(val-v[i],i+1));
    return cache;
}
signed main(){
    FastIO;
    cin>>n>>W;
    rep(i,1,n) cin>>w[i]>>v[i],V+=v[i];
    memset(dp,-1,sizeof dp);
    rec(V,1);
    int ans=0;
    rep(i,1,V){
        rep(j,1,n) if(dp[i][j]!=-1 and dp[i][j]<=W) ans=i;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 45952
from itertools import accumulate

N, W = map(int, input().split())
d = {i: [] for i in range(4)}
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        w0 = w
    w -= w0
    d[w].append(v)

wv = [[] for _ in range(4)]
for k, v in d.items():
    v.sort(reverse=True)
    v = [0] + v
    wv[k] = tuple(accumulate(v))

# w1をc1こ入れる
# w2をc2個入れる...
ans = 0
for c0, v0 in enumerate(wv[0]):
    for c1, v1 in enumerate(wv[1]):
        for c2, v2 in enumerate(wv[2]):
            for c3, v3 in enumerate(wv[3]):
                weight = w0 * (c0 + c1 + c2 + c3) + c1 + c2 * 2 + c3 * 3
                val = v0 + v1 + v2 + v3
                if weight > W:
                    continue
                ans = max(ans, val)

print(ans)


Measured memory_bytes: 3064
#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <tuple>
#include <vector>

using namespace std;

namespace
{

int reverse(int n)
{
	int res = 0;
	while (n != 0) {
		res *= 10;
		res += n % 10;
		n /= 10;
	}

	return res;
}

}

int main()
{
	int a, b, c, d;
	std::cin >> a >> b >> c >> d;

	int e = std::max(a, c), f = std::min(b, d);
	int res = 0;
	if (e <= f)
		res = f - e;

	std::cout << res << std::endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define mod 1000000007
#define mod2 1000000000
#define mod1 998244353
#define lol ios_base::sync_with_stdio(false);cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define F(i, n) for (ll (i) = 0; (i) < (n); (i)++)
#define pb push_back
#define pf push_front
#define mp make_pair
#define f first
#define ss second
int main()
{
    ll n;cin >> n;
    unsigned ll ans = 0;
    for(ll i=1;i<=n;i++)
    {
        ll cnt = n/i;
        ans = ans + ((i)*(cnt+1)*(cnt))/2;
    }
    cout << ans << endl;
    
}
    

Measured memory_bytes: 3636
import std.stdio;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;

void main() {
    string str = readln.chomp;
    string ans = "";
    string[] boin = ["w", "", "k", "s", "t", "n", "h", "m", "y", "r"];
    string[] shiin = ["a", "i", "u", "e", "o"];
    for (int i=0; i<str.length; i+=2) {
        if (str[i..i+2] == ['0', 'U']) {
            ans ~= "nn";
        } else {
            ans ~= boin[str[i]-'0'];
            switch(str[i+1]) {
            case 'T': ans ~= shiin[0]; break;
            case 'L': ans ~= shiin[1]; break;
            case 'U': ans ~= shiin[2]; break;
            case 'R': ans ~= shiin[3]; break;
            case 'D': ans ~= shiin[4]; break;
            default:
            }
        }
    }
    ans.writeln;
}

Measured memory_bytes: 2496
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <limits>
#include <cassert>

#define seq(i, n) for (int i = 0; i < (n); i++)
#define seq2(i, f, t) for (int i = (f); i < (t); i++)
#define rev(i, n) for (int i = (n); i >= 0; i--)
#define rev2(i, f, t) for (int i = (f); i >= (t); i--)
#define all(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;

int solve(int r) {
  return 3 * r * r;
}

int main() {
  #ifdef TEST
    solve();
  #else
    int r;
    cin >> r;
    cout<<solve(r)<<endl;;
  #endif

  return 0;
}


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

using namespace std;

vector<string> split(const string &s, char delim) {
  vector<string> elems;
  string item;
  for (char ch: s) {
    if (ch == delim) {
      if (!item.empty()) {
        elems.push_back(item);
      }
      item.clear();
    }
    else {
      item += ch;
    }
  }
  if (!item.empty()) {
    elems.push_back(item);
  }
  return elems;
}

string to_str_with_zero(int i, int w) {
  ostringstream sout;
  sout << std::setfill('0') << std::setw(w) << i;
  string s = sout.str();
  return s;
}

int letter_to_int(char c) {
  return tolower(c) - 'a';
}

bool array_equal(vector<int> a1, vector<int>a2) {
  if (a1.size() != a2.size()) {
    return false;
  }
  for (int i=0; i<a1.size(); i++) {
    if (a1.at(i) != a2.at(i)) {
      return false;
    }
  }
  return true;
}

int gcd(int a, int b) {
  if (a == b) {
    return a;
  }
  else if (a > b) {
    return gcd(a - b, b);
  }
  else {
    return gcd(a, b - a);
  }
}

char int_to_char(int a) {
  if (a == -1) {
    return 'z';
  }
  else {
    return 'a' + a;
  }
}

long nCr(int n, int r) {
    long ans = 1;
    for (int i = n; i > n - r; --i) {
        ans = ans*i;
    }
    for (int i = 1 ; i < r + 1; ++i) {
        ans = ans / i;
    }
    return ans;
}

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

int divide_count(int a, int divider) {
  int r = 0;
  while(a % divider == 0) {
    a /= divider;
    r++;
  }
  return r;
}

int main() {
  std::cout << std::setprecision(9);
  int n;
  cin >> n;

  vector<pair<double, double>> p(n);
  for(int i=0; i<n; i++) {
    cin >> p[i].first >> p[i].second;
  }

  double ans = 0;
  for(int i=0; i<n; i++) {
    for(int j=i+1; j<n; j++) {
      ans += sqrt(pow(p[i].first - p[j].first, 2) + pow(p[i].second - p[j].second, 2));
    }
  }
  ans *= 2;
  ans /= n;

  cout << ans << endl;
}

Measured memory_bytes: 3848
#include<bits/stdc++.h>
#define ll long long
#define fast ios::sync_with_stdio(false); cin.tie(0);
#define f(i,s,e) for(ll i=s;i<e;i++)
#define pb(x) push_back(x)
#define mp make_pair
#define mod 1000000007
#define all(x) x.begin(),x.end()
using namespace std;
int dp[3001][3001];
string s,t;

int main(){
    fast;

    cin>>s>>t;

    for(int i=0;i<=s.size();i++)
        dp[i][0]=0;
    for(int i=0;i<=t.size();i++)
        dp[0][i]=0;

    for(int i=1;i<=s.size();i++){
        for(int j=1;j<=t.size();j++){
            if(s[i-1]==t[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }

    int ind = dp[s.size()][t.size()];
    char anss[ind+1];
    anss[ind]='\0';

    int i=s.size();int j=t.size();

    while(i>0 && j>0){

        if(s[i-1]==t[j-1]){
            anss[ind-1]=s[i-1];
            i--;
            j--;
            ind--;
        }

        else if(dp[i-1][j]>dp[i][j-1])
            i--;
        else
            j--;
    }

    cout<<anss;

}


Measured memory_bytes: 35456
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace E
{
    class Program
    {
        static void Main(string[] args)
        {
            string line = Console.ReadLine();
            string[] strs = line.Split(' ');
            int X = int.Parse(strs[0]);
            int Y = int.Parse(strs[1]);
            int A = int.Parse(strs[2]);
            int B = int.Parse(strs[3]);
            int C = int.Parse(strs[4]);

            List<int> P = new List<int>();
            List<int> Q = new List<int>();
            List<int> R = new List<int>();
            line = Console.ReadLine();
            strs = line.Split(' ');
            for(int i = 0; i < A; i++)
            {
                P.Add(int.Parse(strs[i]));
            }
            line = Console.ReadLine();
            strs = line.Split(' ');
            for (int i = 0; i < B; i++)
            {
                Q.Add(int.Parse(strs[i]));
            }
            line = Console.ReadLine();
            strs = line.Split(' ');
            for (int i = 0; i < C; i++)
            {
                R.Add(int.Parse(strs[i]));
            }
            P.Sort((a,b) => b - a);
            Q.Sort((a, b) => b - a);
            R.Sort((a, b) => b - a);
            // PからX個取って、入れる
            List<int> ALL = new List<int>();
            for(int i = 0; i < X; i++)
            {
                ALL.Add(P[i]);
            }
            for (int i = 0; i < Y; i++)
            {
                ALL.Add(Q[i]);
            }
            //下位を入れ替えていく
            ALL.Sort();
            for(int i = 0; i < ALL.Count && R.Count > 0; i++)
            {
                if (ALL[i] < R[0])
                {
                    ALL[i] = R[0];
                    R.RemoveAt(0);
                }
            }
            long sum = 0;
            for(int i = 0; i < ALL.Count; i++)
            {
                sum += ALL[i];
            }
            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 42652
import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        long a = sc.nextLong();
        long b = sc.nextLong();
        long c = sc.nextLong();
        long k = sc.nextLong();
        long ans = k % 2 == 0 ? a - b : b - a;
        if (ans > 1000000000000000000L) {
            System.out.println("Unfair");
        } else {
            System.out.println(ans);
        }
    }



    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            }else{
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
        String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        long nextLong() {
            if (!hasNext()) throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while(true){
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                }else if(b == -1 || !isPrintableChar(b)){
                    return minus ? -n : n;
                }else{
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }
        int nextInt() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
            return (int) nl;
        }
        public double nextDouble() { return Double.parseDouble(next());}
    }

}


Measured memory_bytes: 21332
N,L = list(map(int, input().split()))
m = 1000000000
k = 0
s = 0

for i in range(1,N+1):
    h = abs(L+i-1) 
    if h <= m :
        m = h
        k = i

for i in range(1,N+1):
    if i != k:
        s = s + L + i - 1
        
print(s)

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

int main()
{
    int a, b, x, y;
    cin >> x >> y;

    a = 4 * x - y;
    b = -2 * x + y;

    if(a >= 0 && a % 2 == 0 && b >= 0 && b % 2 == 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    
    return 0;
} 

Measured memory_bytes: 3628
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;class Program
{
	
	static void Main(string[] args)
	{
        //var exStdIn = new System.IO.StreamReader( "stdin.txt" );System.Console.SetIn( exStdIn );
		//const long inf = 100000000000000;
		
		var rck = Console.ReadLine().Split().Select(long.Parse).ToArray();
		long r = rck[0], c = rck[1],k = rck[2];
		var map = new long[r, c];
		for (int i = 0; i < k; i++)
		{
			var rcv = Console.ReadLine().Split().Select(long.Parse).ToArray();
			map[rcv[0]-1, rcv[1]-1] = rcv[2];
		}
		var dp = new long[r, c, 4];

		dp[0,0,0] = 0;
		dp[0,0,1] = map[0, 0];
		for (int ri = 0; ri < r; ri++)
		{
			for (int ci = 0; ci < c; ci++)
			{
				for (int ni = 0; ni < 4; ni++)
				{
					if(ri<r-1){
						dp[ri+1,ci,1] = Max(dp[ri+1,ci,1], dp[ri,ci,ni]+map[ri+1,ci]);
						dp[ri+1,ci,0] = Max(dp[ri+1,ci,ni], dp[ri,ci,ni]);
					}
					if(ci<c-1){
						if(ni<3)dp[ri,ci+1,ni+1] = Max(dp[ri,ci+1,ni+1], dp[ri,ci,ni]+map[ri,ci+1]);
						dp[ri,ci+1,ni] = Max(dp[ri,ci+1,ni], dp[ri,ci,ni]);
					}
				}
			}
		}
		long ans = Max(Max(dp[r-1, c-1, 0], dp[r-1, c-1, 1]), Max(dp[r-1, c-1, 2], dp[r-1, c-1, 3]));
		Console.WriteLine(ans);
	}
}


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

void Aout(vector <double> A, int n){
	for (int i=0; i<n; i++){
		if (i!=0) cout<<" ";
		cout<<A[i];
	}
	cout<<endl;
}

void insertionsort(vector <double> A, int n){
	double key;
	int i;
	for (int j=1; j<n; j++){
		key = A[j];
		i = j-1;
		while (i>=0){
			if (A[i] <= key) break;
			A[i+1] = A[i];
			i--;
		}
		A[i+1] = key;
		Aout(A, n);
	}
}

int main(void){
	int n;

	cin>>n;
	vector <double> A(n);

	for (int i=0; i<n; i++)
		cin>>A[i];
	Aout(A, n);
	insertionsort(A, n);

	return 0;
}

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

int main(){
    int N;
    cin >> N;
    vector<int> l;
    for(int i = 0; i < N; i++){
        int a; cin >> a;
        l.push_back(a);
    }

    sort(l.begin(), l.end());
    int count = 0;
    for(int i = 0; i < N; i++){
        for(int j = i + 1; j < N; j++){
            for(int k = j + 1; k < N; k++){
                if(l[i] == l[j] || l[i] == l[k] || l[j] == l[k]) continue;
                if(l[i] + l[j] > l[k]) count++;
            }
        }
    }
    cout << count;
}



Measured memory_bytes: 3148
# 周期的にループする明日の天気を予測してください

# ループする関数がわからんかったから調べた
# 結果　ループする必要なし

# for (変数名）in (イテラブル）:
#    （コードブロック）

today = input ()

if today == "Sunny":
    print("Cloudy")
elif today == "Cloudy":
    print("Rainy")
else:
    print("Sunny")



Measured memory_bytes: 9024
#include <bits/stdc++.h>
using namespace std;
 
 
int main() {
 
  int64_t n;
  cin>>n;

  map<int64_t , int64_t, greater<int64_t>> a;
  for(int i=0;i<n;i++){
    int64_t wk;
    cin>>wk;

    if(a.count(wk))
      a.at(wk)++;
    else
      a[wk]=1;
  }

  // 大きい順に確認
  int64_t side1=0,side2=0;
  bool found=false;
  for (auto p : a) {
    auto k = p.first;
    auto v = p.second;

    if(v/2>=2 && found==false){
      side1=k;
      side2=k;
      break;
    }else if(v/2>=1 && found==false){
      side1=k;
      found=true;
    }else if(v/2>=1 && found==true){
      side2=k;
      break;
    }
  }

  if(side1==0 && side2==0)
    cout<<0<<endl;
  else
    cout<<side1*side2<<endl;

	return 0;
}

Measured memory_bytes: 9728
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<cstring>
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i = 0;i < (n);++i)
#define reps(i,n) for(int i = 1;i <= (n);++i)
using namespace std;
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	int a;
	cin >> a;
	int maxv = a;
	rep(i,n-1){
		cin >> a;
		if(maxv - a >= 2){
			cout << "No\n";
			return 0;
		}
		maxv = max(a,maxv);
	}
	cout << "Yes\n";
	return 0;
}

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

// <=50000
int a[20000];
int b[20000];
int res[40000];
int n,m;
int q=10000;
int main(){
	string s;
//	cin.tie(0);ios::sync_with_stdio(false);
	while(cin>>s){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		int fu=0;
		int k=1,t=0;
		n=m=1;
		if(s[0]=='-')fu^=1,s=s.substr(1,s.length()-1);
		for(int i=0;i<s.length();i++){
			a[n]+=(s[s.length()-i-1]-'0')*k;
			k=k*10;
			if(i%4==3||i+1==s.length()){
				k=1;n++;
			}
		}
		reverse(a+1,a+n);
		cin>>s;
		if(s[0]=='-')fu^=1,s=s.substr(1,s.length()-1);
		k=1;
		for(int i=0;i<s.length();i++){
			b[m]+=(s[s.length()-i-1]-'0')*k;
			k=k*10;
			if(i%4==3||i+1==s.length()){
				k=1;m++;
			}
		}
		reverse(b+1,b+m);
		n--;m--;
		for(int i=0;i<=n+m;i++)res[i]=0;
		if(fu&&!((n==1&&a[1]==0)||(m==1&&b[1]==0)))cout<<"-";
//		if(fu)cout<<"-";
		for(int i=n;i>0;i--){
			for(int j=m;j>0;j--){
				res[i+j]+=a[i]*b[j];
				if(res[i+j]>=q){
					res[i+j-1]+=res[i+j]/q;
					res[i+j]%=q;
				}
			}
		}
		for(int i=m+n;i>0;i--)if(res[i]>=q){
			res[i-1]+=res[i]/q;
			res[i]%=q;
		}
		bool ok=0;
		for(int i=1;i<=n+m;i++){
			if(ok){
				printf("%04d",res[i]);
				continue;
			}
			if(res[i]!=0||(i==n+m)){
				ok=1;
				printf("%d",res[i]);
				continue;
			}
		}cout<<endl;
	}
	
	return 0;
}







Measured memory_bytes: 3508
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

typedef long long llint;

int n, m;
unordered_map<int, int> mp;

llint ans = 0;

int main() {
    cin >> n >> m;
    int am = 0;

    mp[0] = 1;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        am = (am + a) % m;
        if (mp.find(am) == mp.end()) {
            mp[am] = 1;
        } else {
            mp[am]++;
        }
    }

    for (auto it = mp.begin(); it != mp.end(); it++) {
        llint l = it->second;
        ans += l * (l - 1) / 2;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3596
S = input()
K = int(input())

def calc(S):
  ret = 0
  seq = 1
  for i in range(1,len(S)):
    if S[i-1] == S[i]:
      seq += 1
    else:
      ret += seq // 2
      seq = 1
  ret += seq // 2
  return ret
## pK + q（K-1)  として解けるきがします
## pK + q


if S[0] * len(S) == S:
  # 全部おなじだったら
  print((len(S) * K) // 2)
elif K < 1000:
  print(calc(S*K))
else:
  x1 = calc(S)    # p+q
  x2 = calc(S*2)  #2p+q
  print((x2-x1) * K + 2*x1 - x2)
  


Measured memory_bytes: 9120
# https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_A
import heapq

N, M, r = list(map(int, input().split()))

D = {}
for i in range(N):
    D[i] = []

for _ in range(M):
    s, t, d = list(map(int, input().split()))
    D[s].append((t, d))

A = []
heapq.heappush(A, (0, r))

INF = float('inf')
results = [INF for _ in range(N)]
results[r] = 0

while A:
    cost, a = heapq.heappop(A)
    for t, d in D[a]:
        next_cost = cost + d
        if next_cost < results[t]:
            results[t] = next_cost
            heapq.heappush(A, (next_cost, t))

for result in results:
    if result == INF:
        print('INF')
    else:
        print(result)



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

#define pb push_back
#define ppp pop_back
#define pii pair<int,int>
#define fi first
#define se second

const int N = 2e5 + 5;
const ll inf = 1e18;

vector<pii> open[N], close[N];
ll dp[N], a[N];
ll t[4*N], ch[4*N];
ll good_value = - inf;
int n;

ll merge(ll a, ll b) {
	return max(a, b);
}

void build() {
	for (int i=0; i<4*N; i++) t[i] = ch[i] = 0;
}

void push(int v, int l, int r) {
	if (!ch[v]) return;
	t[v] += ch[v];
	if (l < r) {
		ch[v+v] += ch[v];
		ch[v+v+1] += ch[v];
	}
	ch[v] = 0;
}

void upd(int v, int l, int r, int L, int R, ll x) {
	push(v, l, r);
	if (l > R || L > r) return;
	if (L <= l && r <= R) {
		ch[v] += x;
		push(v, l, r);
		return;
	}
	int mid = (l + r) / 2;
	upd(v+v, l, mid, L, R, x);
	upd(v+v+1, mid+1, r, L, R, x);
	t[v] = merge(t[v+v], t[v+v+1]);
}

void upd(int L, int R, ll x) {
	upd(1, 1, n, L, R, x);
}

ll get(int v, int l, int r, int L, int R) {
	push(v, l, r);
	if (l > R || L > r) return good_value;
	if (L <= l && r <= R) return t[v];
	int mid = (l + r) / 2;
	return merge(get(v+v, l, mid, L, R), get(v+v+1, mid+1, r, L, R));
}

ll get(int L, int R) {
	return get(1, 1, n, L, R);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int m;
	cin >> n >> m;
	for (int i=1; i<=m; i++) {
		int l, r, a;
		cin >> l >> r >> a;
		open[l].pb({r, a});
		close[r].pb({l, a});
	}
	a[0] = 0;
	for (int i=1; i<=n; i++) {
		a[i] = a[i-1];
		for (pii cur : open[i]) a[i] += cur.se;
		for (pii cur : close[i-1]) a[i] -= cur.se;
	}
	build();
	for (int i=1; i<=n; i++) {
		for (pii cur : open[i]) {
			upd(i, cur.fi, -cur.se);
		}
		dp[i] = max(a[i], a[i] + get(1, i-1));
		upd(i, i, dp[i]);
		for (pii cur : close[i]) {
			upd(cur.fi, i, cur.se);
		}
	}
	ll ans = 0;
	for (int i=1; i<=n; i++) ans = max(ans, dp[i]);
	cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 37760
import sys

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


def solve():
    A, B, C = il()
    m = max([A, B, C])
    diff = [m - A, m - B, m - C]
    c = 0
    for i, d in enumerate(diff):
        div_2 = d // 2
        if div_2 > 0:
            c += d // 2
            diff[i] -= 2 * div_2
    num_of_1 = diff.count(1)
    if num_of_1 == 1:
        c += 2
    elif num_of_1 == 2:
        c += 1
    return c


if __name__ == "__main__":
    print(solve())


Measured memory_bytes: 3064
import sys
import math
from collections import defaultdict

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

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

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

N,K = II()
R,S,P = II()
T = str(input())

def calc(c):
    if c=='r':
        return P
    elif c=='s':
        return R
    else:
        return S

d = defaultdict(list)
for i in range(N):
    d[i%K].append(T[i])

ans = 0
for i in range(K):
    for j,c in enumerate(d[i]):
        if j==0:
            ans += calc(c)
            before = c
        else:
            if c!=before:
                ans += calc(c)
                before = c
            else:
                before = 'z'

print(ans)

Measured memory_bytes: 61296