akhauriyash/Code-Regression huggingface dataset:
#include<math.h>
#include<cmath>
#include<bitset>
#include<stdio.h>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<iostream>
#include<utility>
using namespace std;
int main(){
  const int INF=1000000000;
  int n,m,a[1010],b,c[1010],d,i,j,dp[(1<<13)];
  scanf("%d %d\n",&n,&m);
  for(i=0;i<m;i++){
    c[i]=0;
  }
  for(i=0;i<(1<<n);i++){
    dp[i]=INF;
  }
  for(i=0;i<m;i++){
    scanf("%d %d\n",&a[i],&b);
    for(j=0;j<b;j++){
      scanf("%d ",&d);
      d--;
      c[i]|=(1<<d);
    }
  }
  dp[0]=0;
  for(i=0;i<m;i++){
    for(j=0;j<(1<<n);j++){
      dp[j|c[i]]=min(dp[j|c[i]],dp[j]+a[i]);
    }
  }
  if(dp[(1<<n)-1]==INF){
    printf("-1\n");
    return 0;
  }
  printf("%d\n",dp[(1<<n)-1]);
  return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<time.h>
#include<cassert>

using namespace std;
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
#define EPS (1e-13)
#define bit(n,k) ((n>>k)&1)
const ll Mod = 1e9 + 7;
const ll mod = 998244353;
struct H {
	ll x, y;
	bool operator<(const H& b) const {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H& b) const {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H& b) const { return x == b.x && y == b.y; }
	bool operator!=(const H& b) const { return (*this) != b; }
};
struct P {
	ll pos, cost;
	bool operator<(const P& b) const { return cost < b.cost; }
	bool operator>(const P& b) const { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E& b) const { return cost < b.cost; }
	bool operator>(const E& b) const { return cost > b.cost; }
};
template<typename T, typename U>
void chmin(T& a, U b) {
	if (a > b) a = b;
}
template<typename T, typename U>
void chmax(T& a, U b) {
	if (a < b) a = b;
}
template<typename T>
T max_0(T a) {
	if (a < 0) return 0;
	return a;
}
template<typename T>
T min_0(T a) {
	if (a > 0) return 0;
	return a;
}
ll read() {
	ll u;
	ll k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j % i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
ll bitcount(ll x) {
	int sum = 0;
	for (int i = 0; i < 20; i++)
		if ((1ll << i) & x) sum++;
	return sum;
}
/*ll fact_[200000];
ll comb(ll x, ll y, ll mod = Mod) {
	if (!fact_[0]) {
		fact_[0] = 1;
		for (int i = 1; i < 200000; i++) {
			fact_[i] = fact_[i - 1] * i % mod;
		}
	}
	if (x < y) return 0;
	return mod_pow(fact_[x], mod, mod) *
		mod_pow(fact_[x - y], mod - 2, mod) % mod *
		mod_pow(fact_[y], mod - 2, mod) % mod;
}//xCy*/
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
int n, k;
string s;
signed main() {
	cin >> n >> k >> s;
	int sum = 0;
	for (int i = 0; i < n; ) {
		int j = i;
		while (j < n && s[i] == s[j]) {
			j++;
		}
		sum++;
		i = j;
	}
	cout << n - max(1ll, sum - 2 * k) << endl;
}

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

int main() {
    int n;
    string s;
    cin >> n >> s;
    
    int count = 0;
    
    rep(i,n-2) {
    if ((s.at(i) == 'A' && s.at(i + 1) == 'B') && s.at(i +2) == 'C') {
    count++;
     }
    }
cout << count;
}

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

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pf printf
#define sc scanf
#define sf(num) scanf("%d",&num)
#define sff(num1,num2) scanf("%d %d",&num1,&num2)
#define sfff(num1,num2,num3) scanf("%d %d %d",&num1,&num2,&num3);
#define sl(num) scanf("%lld",&num)
#define sll(num1,num2) scanf("%lld %lld",&num1,&num2)
#define slll(num1,num2,num3) scanf("%lld %lld %lld",&num1,&num2,&num3);
#define rep(i,n) for(i=1;i<=n;i++)
#define rep0(i,n) for(i=0;i<n;i++)
#define reps(i,a,n) for(i=a;i<=n;i++)
#define pb push_back
#define mpp make_pair
#define MOD 1000000007
#define fi first
#define se second
#define N 100005
#define mem(ara,n) memset(ara,n,sizeof(ara))
#define memb(ara) memset(ara,false,sizeof(ara))
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define pi pair<int,int>
#define pii pair<pair<int,int>,pair<int,int> >
#define db(x) cout<<#x<<" :: "<<x<<"\n";
#define dbb(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define fr freopen("input.txt","r",stdin);
#define fw freopen("output.txt","w",stdout);
#define TIME cerr<<"Time : "<<(double)clock()/(double)CLOCKS_PER_SEC<<"s\n";
typedef long long int ll;
using namespace std;
int main()
{
    int i,n,k;
    sf(n);
    vector<int>vec;
    rep0(i,n)
    {
        sf(k);
        vec.pb(k);
    }
    sort(all(vec));
    k=n/2;
    pf("%d\n",vec[k]-vec[k-1]);
}


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

int main() {
  string b; 
  cin >> b;
  if (b=="A"){
    cout << "T" << endl;
  }
  else if (b=="T"){
    cout << "A" << endl;
  }
  else if (b=="C"){
    cout << "G" << endl;
  }
  else if (b=="G"){
    cout << "C" << endl;
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
long long a,b,c,x,y,s,minn,maxx,z,ans;
int main()
{
	cin>>a>>b>>c>>x>>y;
	s=a+b;
	minn=min(x,y);
	maxx=max(x,y);
	z=maxx-minn;
	if(s>=2*c)
	ans+=minn*2*c;
	else 
	ans+=minn*s;
	if(a<=2*c&&x==maxx)
	{
		ans+=z*a;
	}
	else if(a>2*c&&x==maxx)
	{
		ans+=z*2*c;
	}
	else if(b>2*c&&y==maxx)
	{
		ans+=z*2*c;
	}
	else if(a<=2*c&&y==maxx)
	{
		ans+=z*b;
	}	
	
	
	cout<<ans;
	return 0;
	
} 

Measured memory_bytes: 256
macro_rules! get {
      ($t:ty) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.trim().parse::<$t>().unwrap()
          }
      };
      ($($t:ty),*) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              let mut iter = line.split_whitespace();
              (
                  $(iter.next().unwrap().parse::<$t>().unwrap(),)*
              )
          }
      };
      ($t:ty; $n:expr) => {
          (0..$n).map(|_|
              get!($t)
          ).collect::<Vec<_>>()
      };
      ($($t:ty),*; $n:expr) => {
          (0..$n).map(|_|
              get!($($t),*)
          ).collect::<Vec<_>>()
      };
      ($t:ty ;;) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.split_whitespace()
                  .map(|t| t.parse::<$t>().unwrap())
                  .collect::<Vec<_>>()
          }
      };
      ($t:ty ;; $n:expr) => {
          (0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()
      };
}

use std::cmp::min;

fn main() {
    // 入力
    let (A, B, C) = get!(i64, i64, i64);

    let ans = min(B / A, C);

    // 出力
    println!("{}", ans);
}


Measured memory_bytes: 4352
using System;
using System.Collections;
class main{
	public static void Main(){
		string[]str = Console.ReadLine().Split();
		int[] num = new int[3];
		for (int i = 0; i < 3; i++)
		{
			num[i] = int.Parse(str[i]);
		}
		Array.Sort(num);
		Console.WriteLine("{0} {1} {2}", num[0], num[1], num[2]);
	}
}

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

int main(){
  int t,n;
  while(1){
    cin >> t;
    if(t==0) break;
    cin >> n;
    for(int i=0;i<n;i++){
      int s,f;
      cin >> s>> f;
      t-=f-s;
    }
    if(t<=0) cout << "OK"<<endl;
    else cout<<t<<endl;
  }
  
  return 0;
}

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

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

  int cnt=0;
  int maxcnt=0;
  for (long i=0; i<S.length(); i++) {
    if (S[i]=='A' || S[i]=='C' || S[i]=='G' || S[i]=='T') {
      cnt++;
    } else {
      maxcnt=max(maxcnt, cnt);
      cnt = 0;
    }
  }
  
  maxcnt=max(maxcnt, cnt);
  cout << maxcnt << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
const ll MOD = 1000000007;

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000007;
 
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;
  int A[N+1];
  A[0] = 0;
  int pow6 = 6, pow9 = 9;
  for(int i=1;i<=N;i++){
    if(i == pow6){
      pow6 *= 6;
    }
    if(i == pow9){
      pow9 *= 9;
    }
    A[i] = min(A[i-pow6/6], A[i-pow9/9]) + 1;
  }
  cout << A[N] << endl;
}

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


int main() {
  long d;
  cin>>d;
  vector<long>c(26);
  rep(i,26){
    cin>>c.at(i);
  }
  vector<vector<long>>s(d,vector<long>(26));
  rep(i,d){
    rep(j,26){
      cin>>s[i][j];
    }
  }
  vector<long>t(d);
  rep(i,d){
    cin>>t[i];
    t[i]--;
  }
  vector<long>ch(26);
  long tot=0;
  rep(i,d){
    
    
    ch[t[i]]=i+1;
    long mi=0;
    rep(j,26){
      if(j!=t[i]){
        mi+=c[j]*(i+1-ch[j]);
      }
    }
    tot+=s[i][t[i]]-mi;
    cout<<tot<<endl;
  }
  
}





Measured memory_bytes: 3684
import java.util.Scanner;

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

        int n = stdIn.nextInt();
        int m = stdIn.nextInt();
        int dp[] = new int[n + 2];
        dp[n + 1] = 0;
        dp[n] = 1;
        for (int i = 0; i < m; i++)
            dp[stdIn.nextInt()] = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (dp[i] == -1)
                dp[i] = 0;
            else
                dp[i] = (dp[i + 1] + dp[i + 2]) % 1000000007;
        }
        System.out.println(dp[0]);
    }
}


Measured memory_bytes: 48828
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <tuple>
#include <stack>
#include <bitset>

using namespace std;
typedef long long ll;
const int MOD_P = 1000000000 + 7;
const int MAX_H = 1000 + 2;
const int MAX_W = 1000 + 2;
const int MAX_N = MAX_H * MAX_W;

char grid[MAX_H][MAX_W];
int dp[MAX_N];

vector<int> G[MAX_N];
bool seen[MAX_N];    
vector<int> order;   

void rec(int v) {
  seen[v] = true;
  for (int i = 0; i < G[v].size(); i++) {
    int next = G[v][i];
    if (seen[next]) continue;
    rec(next);
  }
  order.push_back(v);
  
}

int main() {

  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  
  int H, W;
  cin >> H >> W;
  int N = H * W;
  
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> grid[i][j];
    }
  }

  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      int v = i*W + j;
      if (i + 1 < H && grid[i+1][j] == '.') G[v].push_back( (i+1)*W + j );
      if (j + 1 < W && grid[i][j+1] == '.') G[v].push_back( i*W + (j+1) );
    }
  }

  fill(seen, seen + MAX_N, false);
  for (int v = 0; v < N; v++) {
    if (seen[v]) continue;
    rec(v);
  }
  reverse(order.begin(), order.end());

  fill(dp, dp + MAX_N, 0);
  dp[0] = 1;
  for (int i = 0; i < order.size(); i++) {
    int v = order[i];
    for (int j = 0; j < G[v].size(); j++) {
      int vn = G[v][j];
      dp[vn] += dp[v];
      dp[vn] %= MOD_P;
    }
  }

  cout << dp[N - 1] << endl;
  return 0;
}



Measured memory_bytes: 67548
N=int(input())
F=[int('0b'+''.join(list(input().split(' '))),0) for i in range(N)]
P=[list(map(int,input().split(' '))) for i in range(N)]
ans = -float('inf')
for i in range(1,1024):
    tmp = 0
    for j,k in zip(P,F):
        tmp += j[str(bin(i&k)).count('1')]
    ans = max(tmp,ans)
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <cmath>

int main() {
    int A, B, C, K;
    std::cin >> A >> B >> C >> K;
    
    int ans = (A + B + C) + std::max({A, B, C}) * std::pow(2, K) - std::max({A, B, C});
    std::cout << ans << std::endl;
}

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

using namespace std;
using ll=long long;
using ull=unsigned long long;

typedef pair<int,int>Pi;
typedef pair<long long,long long>P;
typedef pair<long long,P>PP;
typedef pair<P,P>PPP;

const long long MOD=1e9+7;
const long long INF=5e18;
const int di[4]={1,0,-1,0};
const int dj[4]={0,1,0,-1};

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define double long double

string s;

void input(){
	cin>>s;
	return;
}

void solve(){
	if(s[0]=='a')cout<<"square1001"<<endl;
	else cout<<"e869120"<<endl;
	return;
}

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


Measured memory_bytes: 3208
N, K = [int(item) for item in input().split()]
S = [item for item in input()]

def compress(arr):
    """圧縮して消えた人はhappy"""
    cnt_h = 0
    new_arr = []
    comp_arr = ['L']

    #最初は先頭をLにする　この回転はノーカン
    if arr[0] == 'R':
        for item in arr:
            if item == 'L':
                new_arr.append('R')
            else:
                new_arr.append('L')

            prev_item = item
    else:
        new_arr = arr
    # 圧縮操作と圧縮されたかずを数える

    for i in range(1, N):
        if new_arr[i - 1] == new_arr[i]:
            cnt_h += 1
        else:
            comp_arr.append(new_arr[i])

    return [comp_arr, cnt_h] 


def execute(arr, cnt_h, K):
    # 境界を全て反転するために必要な操作回数
    max_rotation = len(arr)//2
    # 全てLになるか反転回数がKに到達するかで終了
    if max_rotation <= K:
        cnt_h += len(arr) - 1
    else:
        cnt_h += 2*K

    return cnt_h

arr, cnt_h = compress(S)
print(execute(arr, cnt_h, K))



Measured memory_bytes: 5532
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef double db;
const int maxn = 1e6 + 10;
int a[3];
int main()
{
   for(int i=0;i<3;i++)
    cin>>a[i];
   sort(a,a+3);
   int cnt=0;
   int temp1=a[2]-a[0];
   int temp2=a[1]-a[0];
   int temp3=a[2]-a[1];
   int mod1=temp1%2;
   int mod2=temp3%2;
   if(!mod1&&!mod2)
    {
        cnt+=temp1/2;
        cnt+=temp3/2;
        cout<<cnt<<endl;
    }
    else if(mod1&&mod2)
    {
        cnt+=temp1/2;
        cnt+=temp3/2;
        cout<<cnt+1<<endl;
    }
   else if (mod1||mod2)
   {
       cnt+=(temp1+temp3+1)/2;
       cout<<cnt+1<<endl;
   }
   else 
   {
    cnt+=(temp1+temp3-1)/2;
    cout<<cnt+1<<endl;
   }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
int max(int a,int b){
  if(a>b) return a;
  return b;
}
int main(){
  int N,K,*cur,NN,*ans;
  scanf("%d %d",&N,&K);
  NN=N*N;
  cur=malloc(sizeof(int)*N);
  ans=malloc(sizeof(int)*N);
  for(int i=0;i<N;i++) scanf("%d",&cur[i]);
  for(int x=0;x<K;x++){
    int *nex,sum;
    sum=0;
    nex=malloc(sizeof(int)*N);
    for(int y=0;y<N;y++) nex[y]=0;
    for(int i=0;i<N;i++){
      int d,l,r;
      d=cur[i];
      l=max(0,i-d);
      r=i+d;
      nex[l]++;
      if(r+1<N) nex[r+1]--;
    }
    for(int i=1;i<N;i++) nex[i]+=nex[i-1];
    cur=nex;
    for(int i=0;i<N;i++) sum+=cur[i];
    if(sum==NN){
      printf("%d",cur[0]);
      for(int i=1;i<N;i++) printf(" %d",cur[i]);
      printf("\n");
      break;
    }
    if(x==K-1){
      printf("%d",cur[0]);
      for(int i=1;i<N;i++) printf(" %d",cur[i]);
      printf("\n");
    }
  }
  return 0;
}


Measured memory_bytes: 34604
program main
  implicit none
  
  integer :: a,b
  read(*,*)a,b
  
  if ((a == 1) .and. (b == 2)) then
    write(*,*)3
  else if ((a == 1) .and. (b == 3)) then
    write(*,*)2
  else if ((a == 2) .and. (b == 1)) then
    write(*,*)3
  else if ((a == 2) .and. (b == 3)) then
    write(*,*)1
  else if ((a == 3) .and. (b == 1)) then
    write(*,*)2
  else if ((a == 3) .and. (b == 2)) then
    write(*,*)1
  end if
end program main

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

#define N 310
ll a[N][N], n, mn[N][N];

struct UF {
	int par[N],rank[N];
	
	void init(int n){
		for(int i = 0; i < n; i++){
			par[i] = i;
			rank[i] = 0;
		}
	}
	
	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}
	
	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		
		if(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = par[x];
			if(rank[x] == rank[y]) rank[y]++;
		}
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}
};
int main(){
	cin>>n;
	rep(i, n) rep(j, n) cin>>a[i][j];
	bool ok = true;
	rep(i, n) rep(j, n) mn[i][j] = 1;
	rep(i, n) rep(j, n) rep(k, n){
		if(a[i][j]>a[i][k]+a[k][j]) ok = false;
		if(a[i][j]==a[i][k]+a[k][j] && i!=k && j!=k) mn[i][j] = 0;
	}
	if(!ok){
		cout<<-1<<endl;
		return 0;
	}
	ll res = 0;
	rep(i, n) rep(j, n) res += mn[i][j]*a[i][j];
	cout<<res/2<<endl;
	/*
	UF uf;
	uf.init(n);
	vector<PP> v;
	rep(i, n) rep(j, i) v.push_back(PP(a[i][j], P(i, j)));
	sort(all(v));
	ll res = 0;
	rep(i, v.size()){
		int x = v[i].snd.fst, y = v[i].snd.snd;
		if(!uf.same(x, y)){
			uf.unite(x, y);
			res += v[i].fst;
		}
	}
	cout<<res<<endl;
	*/
	return 0;
}


Measured memory_bytes: 1664
#include <iostream>
#include <iomanip>
#include <cmath>
#include <functional>
#include <algorithm>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <boost/range/irange.hpp>
#include <boost/container/static_vector.hpp>
#include <boost/utility/string_ref.hpp>

template <class Integer>
auto boost_irange(Integer last) { return boost::irange(static_cast<Integer>(0), last); }
template <class Integer>
auto boost_irange(Integer first, Integer last) { return boost::irange(first, last); }

class input
{
    std::istream& cin;

public:
    input() : cin(std::cin)
    {
        std::cin.tie(nullptr);
        std::ios::sync_with_stdio(false);
    }

    template <class T>
    inline input& operator>>(T& var)
    {
        cin >> var;
        return *this;
    }
    template <class T>
    inline input& operator,(T& var)
    {
        cin >> var;
        return *this;
    }

    template <class T>
    inline T read()
    {
        T var;
        cin >> var;
        return var;
    }

    template <class InputIterator>
    inline void read(InputIterator head, std::size_t n)
    {
        for (std::size_t i = 0; i < n; ++i) {
            cin >> *head;
            ++head;
        }
    }

    template <class T, class F>
    inline void online(std::size_t n, F&& f)
    {
        T var;
        for (std::size_t i = 0; i < n; ++i) {
            cin >> var;
            f(var);
        }
    }
};
template <class T, std::size_t n>
std::istream& operator>>(std::istream& in, std::array<T, n>& var)
{
    for (std::size_t i = 0; i < n; ++i) {
        in >> var[i];
    }
    return in;
}

class output
{
    std::ostream& cout;

public:
    class proxy
    {
        std::ostream& cout;

    public:
        proxy() : cout(std::cout) {}
        ~proxy() { cout << std::endl; }
        template <class T>
        proxy& operator,(T&& val)
        {
            cout << val << ' ';
            return *this;
        }
    };

public:
    output() : cout(std::cout)
    {
        cout << std::fixed << std::setprecision(15);
    }

    template <class T>
    proxy operator<<(T&& val)
    {
        cout << val << ' ';
        return {};
    }
};

int main()
{
    input in;
    output out;

    switch (in.read<char>()) {
    case 'S':
        out << "Cloudy";
        break;
    case 'C':
        out << "Rainy";
        break;
    case 'R':
        out << "Sunny";
        break;
    default:
        break;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
map<string,int>m;
string ss[]={"AC", "WA", "TLE", "RE"};
int main()
{
    int n;
    cin>>n;
    while(n--){
        string s;
        cin>>s;
        m[s]++;
    }

    for(auto x:ss){
        cout<<x<<" x "<<m[x]<<endl;
    }
    return 0;
}



Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main(){
  	int n,k;
  	int r,s,p;
  	string ss;
  	cin >> n >> k >> r >> s >> p >> ss;
  	int ans=0;
  	for(int i=0;i<k;i++){
  		if(ss[i]=='r'){
  			ans+=p;
		}
		else if(ss[i]=='s'){
			ans+=r;
		}
		else{
			ans+=s;
		}
	}
  	for(int i=k;i<n;i++){
  		if(ss[i]==ss[i-k]){
  			ss[i]=' ';
		}
		else{
			if(ss[i]=='r'){
	  			ans+=p;
			}
			else if(ss[i]=='s'){
				ans+=r;
			}
			else{
				ans+=s;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10
#define MAX_N 20000
#define MAX_M 16

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

ll  n, m, b[1000];

int main(){
	while (cin >> m >> n&&n + m){
		ll MAX = -1;
		REP(i, n){
			cin >> b[i];
			MAX = max(MAX, b[i]);
		}
		ll lb = MAX - 1, ub = 1500001;
		while (ub - lb > 1){
			int co = 1;
			ll mid = (lb + ub) / 2;
			ll sum = 0;
			REP(i, n){
				sum += b[i];
				if (sum > mid){
					sum = b[i];
					co++;
				}
			}
			if (co <= m)ub = mid;
			else lb = mid;
		}
		cout << ub << endl;
	}
}

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

using namespace std;
typedef long long ll;
int mod(ll a){
    int c=a%1000000007;
    if(c>=0)return c;
    else return c+1000000007;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
#define inf 100000000/*10^8*/

/////////////////////////////////

int w,h;
int si,sj;

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

int room[25][25];
int ans=0;
int dfs(int x,int y){
    room[x][y]=2;ans++;
    for(int i=0;i<=3;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(0<=xx&&xx<=h-1&&0<=yy&&yy<=w-1&&room[xx][yy]==0)dfs(xx,yy);
    }
    return ans;
}


int main(){
    while(1){
        cin>>w>>h;
        if(w==0)break;
        ans=0;
        for(int i=0;i<=h-1;i++){
            char s[w+1];cin>>s;
            for(int j=0;j<=w-1;j++){
                if(s[j]=='.')room[i][j]=0;
                else if(s[j]=='#')room[i][j]=1;
                else if(s[j]=='@')room[i][j]=2,si=i,sj=j;
            }
        }
        cout<<dfs(si,sj)<<endl;
    }
    return 0;
}



Measured memory_bytes: 3004
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

d,t,s=mp()
if s*t>=d:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 10396
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::str::FromStr;
use std::io::*;
use std::collections::*;
use std::cmp::*;

struct Scanner<I: Iterator<Item = char>> {
    iter: std::iter::Peekable<I>,
}

macro_rules! exit {
    () => {{
        exit!(0)
    }};
    ($code:expr) => {{
        if cfg!(local) {
            writeln!(std::io::stderr(), "===== Terminated =====")
                .expect("failed printing to stderr");
        }
        std::process::exit($code);
    }}
}

impl<I: Iterator<Item = char>> Scanner<I> {
    pub fn new(iter: I) -> Scanner<I> {
        Scanner {
            iter: iter.peekable(),
        }
    }

    pub fn safe_get_token(&mut self) -> Option<String> {
        let token = self.iter
            .by_ref()
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            Some(token)
        }
    }

    pub fn token(&mut self) -> String {
        self.safe_get_token().unwrap_or_else(|| exit!())
    }

    pub fn get<T: FromStr>(&mut self) -> T {
        self.token().parse::<T>().unwrap_or_else(|_| exit!())
    }

    pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.get()).collect()
    }

    pub fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }

    pub fn char(&mut self) -> char {
        self.iter.next().unwrap_or_else(|| exit!())
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.get::<String>().chars().collect()
    }

    pub fn mat_chars(&mut self, row: usize) -> Vec<Vec<char>> {
        (0..row).map(|_| self.chars()).collect()
    }

    pub fn line(&mut self) -> String {
        if self.peek().is_some() {
            self.iter
                .by_ref()
                .take_while(|&c| !(c == '\n' || c == '\r'))
                .collect::<String>()
        } else {
            exit!();
        }
    }

    pub fn peek(&mut self) -> Option<&char> {
        self.iter.peek()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char));
    let mut S: Vec<char> = sc.chars();
    let T: Vec<char> = sc.chars();
    let N = S.len();
    for _ in 0..N {
        let c = S.pop().unwrap();
        S.insert(0, c);
        if S == T {
            println!("Yes");
            return;
        }
    }
    println!("No");
}


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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define LL long long;
#define REP(i,s,N) for (int i=s; i<N; i++)

int main() {
	int A, B;
	char op;
	cin >> A >> op >> B;
	if(op=='+') cout << A+B << endl;
	else cout << A-B << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <stack>
#pragma warning( disable:4996 )
using namespace std;

#define GMAX 1400
int G[GMAX][GMAX];
int T[GMAX][GMAX];

struct Rectangle { int height; int pos; };

int getLargestRectangle(int size, int buffer[])
{
	int maxv = 0;
	stack<Rectangle> S;
	buffer[size] = 0;

	for (int i = 0; i <= size; i++) {
		Rectangle rect;
		rect.height = buffer[i];
		rect.pos = i;
		if (S.empty()) {
			S.push(rect);
		}
		else {
			if (S.top().height < rect.height) {
				S.push(rect);
			}
			else {
				if (S.top().height > rect.height) {
					int target = i;
					while (!S.empty() && S.top().height >= rect.height) {
						Rectangle pre = S.top(); S.pop();
						int area = pre.height * (i - pre.pos);
						maxv = max(maxv, area);
						target = pre.pos;
					}
					rect.pos = target;
					S.push(rect);
				}
			}
		}
	}

	return maxv;
}

int getLargestRectangle(int H, int W)
{
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (G[i][j]) {
				T[i][j] = 0;
			}
			else {
				T[i][j] = (i > 0) ? T[i - 1][j] + 1 : 1;
			}
		}
	}
	int maxv = 0;
	for (int i = 0; i < H; i++) {
		maxv = max(maxv, getLargestRectangle(W, T[i]));
	}
	return maxv;
}

int main()
{
	int H, W;
	scanf("%d %d", &H, &W);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) scanf("%d", &G[i][j]);

	}
	printf("%d\n", getLargestRectangle(H, W));
	return 0;
}


Measured memory_bytes: 18072
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;
const int MAX = 1010;
ll f[MAX], finv[MAX], tbl[MAX][MAX];

ll mod_pow(ll x, ll e) {
  ll v = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) {
      v = v * x % MOD;
    }
    x = x * x % MOD;
  }
  return v;
}

inline ll Comb(int n, int k) {
  if (k < 0 || k > n) {
    return 0;
  }
  return (f[n] * finv[k] % MOD) * finv[n - k] % MOD;
}

void init() {
  f[0] = 1;
  for (int i = 1; i < MAX; i++) {
    f[i] = f[i-1] * i % MOD;
  }
  finv[MAX-1] = mod_pow(f[MAX-1], MOD - 2);
  for (int i = MAX - 2; i >= 0; i--) {
    finv[i] = finv[i+1] * (i + 1) % MOD;
  }
  for (int i = 1; i < MAX; i++) {
    tbl[i][1] = 1;
    for (int j = 2; j < MAX; j++) {
      if (i * j >= MAX) {
        break;
      }
      tbl[i][j] = tbl[i][j-1] * Comb(i * j, i) % MOD;
    }
  }
}

int main() {
  init();
  int N, A, B, C, D;
  cin >> N >> A >> B >> C >> D;
  vector<vector<ll>> dp(N + 1, vector<ll>(N + 1, 0));
  dp[A-1][N] = 1;
  for (int k = A; k <= B; k++) {
    for (int n = 0; n <= N; n++) {
      (dp[k][n] += dp[k-1][n]) %= MOD;
      for (int m = C; m <= D; m++) {
        if (n < k * m) {
          continue;
        }
        ll tmp = (Comb(n, k * m) * tbl[k][m] % MOD) * finv[m] % MOD;  
        (dp[k][n-k*m] += dp[k-1][n] * tmp % MOD) %= MOD;
      }
    }
  }
  cout << dp[B][0] << endl;
  return 0;
}


Measured memory_bytes: 14336
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  vector<int> a(3);
  rep(snip_i, 3) cin >> a.at(snip_i);
  sort(ALL(a));
  int ans = a.at(2) - a.at(1);
  a.at(0) += ans;
  int d = a.at(2) - a.at(0);
  // cerr << ans << d << endl;
  if(d % 2 == 0) ans += d/2;
  else ans += (d+1)/2+1;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
N,W=map(int,input().split())
w=[]
v=[]
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if w[i]<=j:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[N][W])

Measured memory_bytes: 171400
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <list>
#include <fstream>
#include <iomanip>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <bitset>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int

#include <nmmintrin.h>
#ifdef _MSC_VER

#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

struct Edge {
	int from, to;
};

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

	vector<int> ans;
	int al[30001] = {};
	int cur = 3;
	if (n % 2 == 0) {
		ans.push_back(2);
		ans.push_back(3);
		ans.push_back(10);
		ans.push_back(15);
		al[2] = 1;
		al[3] = 1;
		al[10] = 1;
		al[15] = 1;
	}
	else {
		ans.push_back(2);
		ans.push_back(3);
		ans.push_back(25);
		al[2] = 1;
		al[3] = 1;
		al[25] = 1;
	}
	int base = n % 2 ? 30 : 30;
	int rc = base;
	while (ans.size() < n) {
		int a = cur, b = base - cur;

		if (b > 30000) {
			cur = 3;
			rc += n % 2 ? 30 : 6;
			base = rc;
			continue;
		}

		if (a < b && al[a] == 0 && al[b] == 0) {
			bool ok = false;
			if (n % 2) {
				if ((a % 2 == 0 || a % 3 == 0 || a % 5 == 0) && (b % 2 == 0 || b % 3 == 0 || b % 5 == 0))
					ok = true;
			}
			else {
				if ((a % 2 == 0 || a % 3 == 0 || a % 5 == 0) && (b % 2 == 0 || b % 3 == 0 || b % 5 == 0))
					ok = true;
			}
			if (ok) {
				ans.push_back(a);
				ans.push_back(b);
				al[a] = 1;
				al[b] = 1;
			}
		}
		if (a >= b)
			base += n % 2 ? 30 : 30;
		cur++;
	}

	for (auto itr : ans) {
		cout << itr << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <math.h>
#include <climits>

using namespace std;

int N;
int* R;

int solve() {
  int mi = R[0];
  int diff = INT_MIN;
  for (int i = 1; i < N; i++) {
    diff = max(diff, R[i] - mi);

    if (R[i] < mi)
      mi = R[i];
  }
  return diff;
}

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

  int res = solve();
  cout << res << endl;

  return 0;
}

Measured memory_bytes: 1960
#include <bits/stdc++.h>
using namespace std;
int main(){
  int A,B,C,D,E,a,b,c,d,e;
  cin>>A>>B>>C>>D>>E;
  a=(A-1)%10,b=(B-1)%10,c=(C-1)%10,d=(D-1)%10,e=(E-1)%10;
  int m=min({a,b,c,d,e});
  int ans=(A-1)/10*10+(B-1)/10*10+(C-1)/10*10+(D-1)/10*10+(E-1)/10*10+41+m;
  cout<<ans<<endl;
}

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

int main() {
	int n, m, q;
	cin >> n >> m >> q;
	vector<vector<int>> g(n, vector<int>(n));
	rep(i, m) {
		int l, r;
		cin >> l >> r;
		l--, r--;
		g[l][r]++;
	}
	vector<vector<int>> s(n + 1, vector<int>(n + 1));
	rep(i, n) rep(j, n) {
		s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + g[i][j];
	}
	rep(i, q) {
		int l, r;
		cin >> l >> r;
		cout << s[r][r] - s[r][l - 1] - s[l - 1][r] + s[l - 1][l - 1] << endl;
	}
	return 0;
}

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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

int main()
{
    vector<int> v(3);
    REP(i, 3)
    cin >> v[i];
    sort(ALL(v));
    if(v[0]!=v[2]&&(v[0]==v[1]||v[1]==v[2])){
        cout << "Yes" << "\n";
    }else{
        cout << "No"
             << "\n";
    }
    return 0;
}

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



void solve(){
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    /*
    目の前の人が自分と同じ方向を向いている数
    例えば
    LLLRRLLLLRRRRL
    の時、
    2+1+3+3+0.
    結局、同じ記号の長さ-1の総和が幸福度。
    奇数回だけ回転させることは1回回転させることと同じである
    [3,2,4,4,1]のようなリストを作り、
    「３つの要素を選んで合併する」という操作をk回行える
    どこを回転させても幸福の人数は同じ。上の例だと、5パートにわかれていて、
    N=１４
    幸福の人数＝１４−５＝９
    つまり、何パートに分かれているかを計算し、
    それから2*kを引けばいい
    */
    int pointer = 0;
    int count = 1;
    char c = s[0];
    while(pointer < n){
        if(c != s[pointer]){
            count++;
            c = s[pointer];
        }
        pointer++;
    }
    //cout << count << endl;
    cout << min(n-1, n-(count-2*k)) << endl;
}

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

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <list>
#include <fstream>
#include <iomanip>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <nmmintrin.h>
#include <chrono>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

struct Edge {
	int from, to;
};


signed main()
{
	int h, w;
	cin >> h >> w;

	vector<vector<Edge>> g(h * w);
	int wc = 0;
	int mp[51][51] = {};
	REP(i, h) {
		string str;
		cin >> str;
		REP(j, w) {
			if (str[j] == '.')
				mp[i][j] = 1, wc++;
		}
	}


	REP(i, h) {
		REP(j, w - 1) {
			if (mp[i][j] && mp[i][j + 1]) {
				g[i * w + j].push_back({ i * w + j, i * w + j + 1 });
				g[i * w + j + 1].push_back({ i * w + j + 1, i * w + j});
			}
		}
	}

	REP(i, h - 1) {
		REP(j, w) {
			if (mp[i][j] && mp[i + 1][j]) {
				g[i * w + j].push_back({ i * w + j, i * w + j + w });
				g[i * w + j + w].push_back({ i * w + j + w, i * w + j });
			}
		}
	}

	queue<pii> que;
	que.push({0, 0});
	vector<int> al(h * w, -1);
	while (que.size()) {
		pii cur = que.front();
		que.pop();

		if (al[cur.second] != -1) {
			continue;
		}
		al[cur.second] = cur.first;

		for (auto itr : g[cur.second]) {
			if (al[itr.to] == -1)
				que.push({cur.first + 1, itr.to});
		}

	}

	int dis = al[h*w-1];

	if (dis == -1) {
		cout << -1 << endl;
		return 0;
	}

	cout << wc - dis - 1 << endl;

	return 0;
}


Measured memory_bytes: 512
# -*- coding: utf-8 -*-

n = int(input())
a = [int(x) for x in input().split()]

ans = 1e16
for s in (1, -1):
    res, cumsum = 0, 0
    for j in range(n):
        cumsum += a[j]
        if cumsum * s <= 0:
            res += abs(cumsum-s)
            cumsum = s
        s *= -1
    ans = min(ans, res)

print(ans)

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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, int> PILL;
typedef pair<ll, ll> PLL;

const int MAX_N = 1e5+5;
const int M = 1e6;
const ll INF = (ll)(1e18);
const int inf = 1e9;
const ll MOD = 1000000007LL;

void solve() {

}

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());
    int ans = 2*inf;

    for (int i = 1; i <= 100; i++) {
        int cur = 0;
        for (auto it: a) {
            cur += (it - i)*(it-i);
        }
        ans = min(ans, cur);
    }

    cout << ans;








    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <bitset>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include<iomanip>

#define i64 int64_t
#define ff(ii,nn,mm) for(int ii=nn;ii<mm;ii++)
#define ffrvs(ii,nn,mm) for(int ii=nn;ii>=mm;ii--)
#define srt(vvv) sort(vvv.begin(),vvv.end())
#define srtrvs(vvv) reverse(vvv.begin(),vvv.end())
#define Graph vector<vector<int>>

i64 inf = 1000000007;
i64 giant = 4000000000000000037;

using namespace std;



//メモリ置き場


//inputします
void input() {
	
}

//ライブラリ置き場

//main
int main() {
	input();
	int n, m;
	cin >> n >> m;
	int ans = n * (n - 1) + m * (m - 1);
	ans /= 2;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int[] ary = new int[n];
        for (int i = 0; i < n; i++) {
            ary[i] = Integer.parseInt(sc.next());
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                ans += ary[i] * ary[j];
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 21588
import java.util.*;
  
public class Main {
    Scanner sc = new Scanner(System.in);
  
    public static void main(String[] args) {
        new Main(); 
    }
  
    public Main() {
        new B().doIt();
    }
    class B{
    	int a[] = new int [1000001];
    	ArrayList<Integer> array = new ArrayList<Integer>();
    	ArrayList<Integer> array2 = new ArrayList<Integer>();
        void doIt(){
        	for(int i = 1;i <= 100;i++){
        		int num = i*i*i;
        		array2.add(i*i*i);
        		a[num] = i;
        	}
        	for(int i = 1;i <= 1000;i++){
        		int num = i*i;
        		array.add(i*i);
        		if(a[num] == 0 || a[num] > i){
        			a[num] = i;
        		}
        	}
        	for(int i = 0;i < 1000;i++){
        		for(int j = 0;j < 100;j++){
        			int num = array.get(i) + array2.get(j);
        			if(num > 1000000)break;
        			else if(a[num] == 0 || a[num] > i+j+2){
        				a[num] = i+j+2;
        			}
        		}
        	}
        	for(int i = 1;i <= 1000000;i++){
        		if(a[i] == 0)a[i] = a[i-1]+1;
        		else if(a[i] > a[i-1])a[i] = a[i-1] + 1;
        	}
        	while(true){
        		int n = sc.nextInt();
        		if(n == 0)break;
        		System.out.println(a[n]);
        	}
        }
    }
}

Measured memory_bytes: 40976
format :: Int -> Int -> String
format i j = show i ++ " " ++ show j

solve (s:ss:sss) i j =
    if s == ss
      then format i j
      else if sss == []
             then format (-1) (-1)
             else if s == head sss
                    then format i $ j + 1
                    else solve (ss:sss) (i + 1) (j + 1)

main = do
  s <- getLine
  putStrLn $ solve s 1 2


Measured memory_bytes: 4988
a = [list(map(int,input().split())) for _ in range(3)]
n = int(input())
b = [int(input()) for _ in range(n)]

#a = [[84, 97, 66], [79, 89, 11], [61, 59, 7]]
#b = [89, 7, 87, 79, 24, 84, 30]
c = set(b)

for i in range(3):
  for j in range(3):
    if a[i][j] in c:
      a[i][j] = 0

ck = 0
for i in range(3):
  if a[i] == [0,0,0]:
    ck = 1
    break
  if ( a[0][i],a[1][i],a[2][i] ) == (0,0,0):
    ck = 1
    break

if ( a[0][0],a[1][1],a[2][2] ) == (0,0,0):
  ck = 1
if ( a[2][0],a[1][1],a[0][2] ) == (0,0,0):
  ck = 1

if ck:
  print('Yes')
else:
  print('No')


Measured memory_bytes: 3064
#include<stdio.h>
#include<stdlib.h>

int gcd(int, int);

int main() {
  int N;
  int *A;
  int *a;
  int *gcd_L, *gcd_R;
  int max_gcd = 1;
  int i;

  scanf("%d", &N);

  A = (int *)malloc((N + 2) * sizeof(int));
  a = A;

  gcd_L = (int *)malloc((N + 2) * sizeof(int));
  gcd_R = (int *)malloc((N + 2) * sizeof(int));

  *a = 0;
  a++;

  for(i = 1; i < N + 1; i++) {
    scanf("%d", a);
    a++;
  }

  *a = 0;

  gcd_L[0] = A[0];
  gcd_R[N+1] = A[N+1];

  for(i = 1; i < N + 1; i++) {
    gcd_L[i] = gcd(gcd_L[i-1], A[i-1]);
  }
  for(i = N; i > 0; i--) {
    gcd_R[i] = gcd(gcd_R[i+1], A[i+1]);
  }
  for(i = 1; i < N + 1; i++) {
    if(gcd(gcd_L[i], gcd_R[i]) > max_gcd) max_gcd = gcd(gcd_L[i], gcd_R[i]);
  }

  free(A);
  free(gcd_L);
  free(gcd_R);

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

  return 0;
}

int gcd(int num1, int num2) {
  int q, r;
  int tmp;

  if(num1 == 0) return num2;
  if(num2 == 0) return num1;

  if(num1 < num2) {
    tmp = num1;
    num1 = num2;
    num2 = tmp;
  }

  while(1) {
    q = num1 / num2;
    r = num1 % num2;
    if(r == 0) break;
    num1 = num2;
    num2 = r;
  }

  return num2;
}


Measured memory_bytes: 1280
#include<iostream>
using namespace std;
int main(){
	int N,W,w,v;
	long value[100001]={0},maxV=0;
	cin>>N>>W;
	for(int j=0;j<N;j++){
		cin>>w>>v;
		for(int i=W-w;i>=0;i--){
			if(value[i]!=0 || i==0){
				value[i+w] = max(value[i+w],value[i]+v);
				maxV = max(value[i+w],maxV);
			}
		}
	}
	cout<<maxV;
	return 0;
}

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

int main() {
    // input from txt （提出時にこの箇所は削除すること）
    ifstream in("input.txt");
    cin.rdbuf(in.rdbuf());

    // cinを高速にするためのおまじない
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    //Write code below
    
    int r;
    
    cin >> r;
    
    cout << 3 * r * r << endl;
}


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

using namespace std;
using ll = long long;

vector<ll> solve(ll r, ll D, ll x2000)
{
    vector<ll> ans;
    ll x = x2000;

    for (int i = 1; i <= 10; ++i)
    {
        x = r*x - D;
        ans.push_back(x);
    }

    return ans;
}

int main()
{
    ios::sync_with_stdio(false);

    ll r, D, x2000;
    cin >> r >> D >> x2000;

    auto ans = solve(r, D, x2000);

    for (auto x : ans)
        cout << x << '\n';

    return 0;
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
n, m = MAP()
print((n-1)*(m-1))

Measured memory_bytes: 5144
n = int(input())
c = [6**i for i in range(1,7)]
c.extend([9**i for i in range(1, 6)])
c = sorted(c)[::-1]
dp = [0]*1000000
for i in range(1,n+1):
    dp[i]=dp[i-1]+1
    for c_ in c:
        if i>=c_:
            dp[i]=min(dp[i],dp[i-c_]+1)
print(dp[n])

Measured memory_bytes: 10868