akhauriyash/Code-Regression huggingface dataset:
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

use std::cmp::{max, min};
use std::collections::BinaryHeap;

fn main() {
    let mut bh: BinaryHeap<i64> = BinaryHeap::new();
    let n: usize = read();
    let m: usize = read();
    let mut bc: Vec<(i64, i64)> = vec![];

    for _ in 0..n {
        bh.push(read::<i64>() * -1);
    }

    for _ in 0..m {
        bc.push((read(), read()));
    }

    bc.sort_by(|x, y| x.1.cmp(&y.1));
    bc.reverse();

    'outer: for i in bc {
        for _ in 0..i.0 {
            let minv = bh.pop().unwrap() * -1;
            if minv >= i.1 {
                bh.push(-minv);
                break 'outer;
            }
            bh.push(-i.1)
        }
    }

    // let mut ans = 0;
    println!("{}", -bh.iter().sum::<i64>());
}


Measured memory_bytes: 4996
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll=long long;

const ll INF = 1LL << 60;

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

template<typename T> bool chmin(T& a, T b) {return a > b ? a = b, true : false;}
template<typename T> bool chmax(T& a, T b) {return a < b ? a = b, true : false;}

ll dp[100010];

int main(){
    int N;
    cin >> N;
    dp[0] = 0;
    FOR(i,1,100001){
        dp[i] = INF;
        int power = 1;
        while(power <= i){
            chmin(dp[i], dp[i-power]+1);
            power *= 6;
        }
        power = 1;
        while(power <= i){
            chmin(dp[i], dp[i-power]+1);
            power *= 9;
        }
    }
    cout << dp[N] << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(void){
	
  int a;
  char s[256];
  
  char buf[256];
  char buf2[256];
  fgets(buf, 255, stdin);
  fgets(buf2,225,stdin);
  sscanf(buf, "%d\n",&a);
  sscanf(buf2, "%s",&s);
  
  if(a >= 3200){
    printf("%s", s);
  }else {
  	printf("%s", "red");
  }
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#include <set>
#include <math.h>
#define pai 3.14159265358979323846264338327950288;
#define keta(n) cout << fixed << setprecision((n));
using ll = long long;
int main()
{
  int n;
  cin >> n;
  bool judge = false;
  for (int c = 0; c < 25; c++) {
    for (int d = 0; d < 25; d++) {
      if (n == 4 * c + 7 * d) {
        judge = true;
      }
    }
  }
  if (judge == true)
    cout << "Yes" << endl;
  else if (judge == false)
    cout << "No" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int main()
{
  //freopen("1.in","r",stdin);freopen("1.out","w",stdout)
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin>>s;
  s=s.replace(s.find("2017/01/"), 8, "2018/01/");
  cout<<s<<endl; 
  return 0;

}


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

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

constexpr ll LLINF {1001002003004005006};//ll = 9*LLINF
constexpr int INTINF {1000000000};//int = 2*INTINF

#define  rep(i,n)   for(int i = 0; i < (n); ++i)
#define rrep(i,n)   for(int i = 1; i <= (n); ++i)
#define drep(i,n)   for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for(int i = s; i < t;  ++i)

template<typename T>
void maxs(T& x, T&& y) {
  x=std::max(x,y);
}
template<typename T>
void maxs(T& x, T& y) {
  x=std::max(x,y);
}

template<typename T>
void mins(T& x, T&& y) {
  x=std::min(x,y);
}
template<typename T>
void mins(T& x, T& y) {
  x=std::min(x,y);
}

int main() {
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int N, K;
  cin >> N >> K;
  vector<ull> H(N);
  rep(i, N) cin >> H[i];
  std::sort(H.begin(), H.end());
  ull answer {H[K-1] - H[0]};
  rep(i, N) {
    if (i+K>N) break;
    mins(answer, H[i+K-1]-H[i]);
  }
  cout << answer << '\n';
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#define MAXN 200010

int A[MAXN];
int M[MAXN];
int n;

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

        for( int i = 1; i <= n; i++ )
                scanf("%d", &A[i]);

        M[1] = A[1];
        for( int i = 2; i <= n; i++ )
                M[i] = (M[i-1] < A[i]) ? M[i-1] : A[i];

        int res = 0;
        for( int i = 1; i <= n; i++ ){
                if( M[i] == A[i] )
                        res++;
        }

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

        return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
int Gcd(int a,int b){if (b == 0) return a; return Gcd(b , a%b);}
int Lcm(int a, int b){ return a/Gcd(a,b)*b;}
inline int read(){
    int f = 1, x = 0;char ch = getchar();
    while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}
const int maxn = 2e5 + 10;
int sum[maxn];
int main(){
    int n = read();
    string s;
    cin >> s;
    int ans = 0,res = INT_MAX,has = 0;
    for(int i=0; i<n; i++){
        sum[i] = sum[i-1];
        if (s[i] == '.') sum[i]++;
    }
    for(int i=0; i<n; i++){
        if (s[i] == '#'){
            res = min(sum[n-1]-sum[i]+has,res);
            has++;
        }
    }
    res = min(has,res);
    if (res == INT_MAX){
        cout << 0 << endl;
    }else cout << res << endl;
    return 0;
}

Measured memory_bytes: 1412
#include<stdio.h>
#include<iostream>
using namespace std;

int main()
{
    int n,x[100]={0};
    while(cin>>n){
        int i,add=0,ans=0;
        for(i=0;i<n;i++) {cin>>x[i];add+=x[i];}
        int y=(int)(add*1.0/n+0.5);
        for(i=0;i<n;i++) ans+=(x[i]-y)*(x[i]-y);
        cout<<ans<<endl;
    }
}



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

int main() {
  double l; cin >> l;

  double x = l / 3.0;

  cout << setprecision(15) << x * x * x << endl;
}


Measured memory_bytes: 256
// https://www.slideshare.net/chokudai/union-find-49066733
#include <vector>
#include <iostream>
#include <set>

struct union_find {
  std::vector<int> parent, rank;
  std::vector<int> size;

  union_find(int n) : parent(n), rank(n), size(n) {
    for (int i = 0; i < n; i++) {
      parent[i] = i;
      rank[i] = 0;
      size[i] = 1;
    }
  }

  int root(int x) {
    if (parent[x] == x) {
      return x;
    } else {
      parent[x] = root(parent[x]);
      return parent[x];
    }
  }

  bool same(int x, int y) {
    return root(x) == root(y);
  }

  void unite(int x, int y) {
    x = root(x);
    y = root(y);

    if (x == y) {
      return;
    }

    // rank and size only means for root nodes
    if (rank[x] < rank[y]) {
      parent[x] = y;
      size[y] += size[x];
    } else if (rank[x] > rank[y]) {
      parent[y] = x;
      size[x] += size[y];
    } else {
      parent[x] = y;
      rank[y] += 1;
      size[y] += size[x];
    }
  }

  void debug() {
    std::cout << "UNION-FIND --- " << std::endl;
    for (int p : parent) {
      std::cout << p << " ";
    }
    std::cout << std::endl;

    for (int p : rank) {
      std::cout << p << " ";
    }
    std::cout << std::endl;

    for (int p : size) {
      std::cout << p << " ";
    }
    std::cout << std::endl;


    std::cout << "-------------- " << std::endl;
  }
};

using namespace std;

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

  union_find uf(n);

  for (int i = 0; i < m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    x -= 1;
    y -= 1;
    uf.unite(x, y);
  }

  set<int> roots;

  for (int i = 0; i < n; i++) {
    roots.insert(uf.root(i));
  }

  cout << roots.size() << endl;
  return 0;
}








Measured memory_bytes: 6144
/*input
18277

*/
 
/*
                                                    ______________
                                                          |       )
                                                          |   )   /
                                                          |______/
                                                    |     |      \
                                                    |     |   )   \
                                                    |_____|_______)
 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <iomanip>
#include <fstream>
#include <stack>

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll , ll> PLL;
typedef long double ld;
 
#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
int mod = 1000000007;
const int inf = 1034567891;
const ll LL_INF = 1234567890123456789ll;
#define PI 3.14159265
#define endl '\n'
#define F first
#define S second
#define debug(x) cout << #x << " = " << x << endl;
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
#define out(container) for (auto it : container) cout << it << " "; cout << endl;
 
 
template < typename T > T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > string toString(T a)       { return to_string(a); }
template < typename T > void toInt(string s, T &x) { stringstream str(s); str >> x;}
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline int powr(int a, ll b){
  int x = 1 % mod;
  while(b){
    if(b & 1) x = mul(x, a);
    a = mul(a, a);
    b >>= 1;
  }
  return x;
}
inline int inv(int a){ return powr(a, mod - 2);}



int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  ll n;
  cin >> n;
  ll m = 0, v = 0, cur = 26;
  while (v < n) {
    v += cur;
    m++;
    cur *= 26;
  }
  cur /= 26;
  v -= cur;
  n -= v;
  n -= 1;
  ll prev = 1;
  string ans = "";
  for (int i = 0; i < m; i++) {
    ans += char('a' + n % 26);
    n /= 26;
  }
  reverse(all(ans));
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    long long H;
    int N;
    cin>>H>>N;
    vector<int>A(N);
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    sort(A.begin(),A.end());
    for(int i=N-1;i>=0;i--){
        H=H-A[i];
        if(H<=0){
            cout<<"Yes"<<endl;
            break;
        }
        if(i==0){
            cout<<"No"<<endl;
        }
    }
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep2(i,m,n) for (int i = (m); i < (n); ++i)
#define rep(i,n) rep2(i,0,n)
#define debug(x) cerr << x << endl
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
template<typename T> struct V : vector<T> { using vector<T>::vector; };
V() -> V<int>;
V(size_t) -> V<int>;
template<typename T> V(size_t, T) -> V<T>;
template<typename T> vector<T> make_vec(size_t n, T a) { return vector<T>(n, a); }
template<typename... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec(ts...))>(n, make_vec(ts...)); }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
const int INF = 1<<30;
const ll LINF = 1LL<<61;
const ll MOD = 1000000007;

int main()
{
    int n;
    cin >> n;
    ll ans = 0;
    for(ll a = 1; a < n; a++)
    {
        ans += (n - 1) / a;
    }
    cout << ans << endl;
}


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

#define MAX 2000001
#define VMAX 10000




int main(){

  unsigned short *A, *B;
  int C[VMAX+1];
  
  int n,i,j;

  scanf("%d",&n);

  A=malloc(sizeof(short)*n+1);
  B=malloc(sizeof(short)*n+1);
  
  for(i=0;i <=VMAX;i++)C[i]=0;

  for(i=0;i<n;i++){
    scanf("%hu",&A[i+1]);
    C[A[i+1]]++;
  }

  for(i=1;i<=VMAX;i++)C[i]=C[i]+C[i-1];

  for(j=1;j<=n;j++){
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }

  for(i=1;i<=n;i++){
    if(i>1)printf(" ");
    printf("%d",B[i]);
  }
  printf("\n");

  return 0;

}



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

using i64 = int_fast64_t;
constexpr i64 inf = 1LL<<60;

template<class T>
bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}

struct edge{
  int to;
  i64 cost;
  edge(){}
  edge(int t,i64 c):to(t),cost(c){}
};
using graph = vector<vector<edge>>;

vector<i64> dijkstra(graph const& adj,int v,int r){
  vector<i64> dist(v,inf);
  using pl = pair<i64,int>;
  priority_queue<pl,vector<pl>,greater<>> que;
  que.emplace(0,r);
  while(!que.empty()){
    i64 c;
    int n;
    tie(c,n) = que.top();
    que.pop();
    if(chmin(dist[n],c))
      for(auto const& nx:adj[n])
        if(dist[nx.to]==inf)
          que.emplace(c+nx.cost,nx.to);
  }
  return dist;
}

signed main(){

  int v,e,r;
  cin>>v>>e>>r;
  graph g(v);
  for(int i=0;i<e;++i){
    int s,t;
    i64 d;
    cin>>s>>t>>d;
    g[s].emplace_back(t,d);
  }

  auto dist = dijkstra(g,v,r);

  for(auto const& res:dist){
    if(res==inf)cout<<"INF"<<endl;
    else cout<<res<<endl;
  }

}


Measured memory_bytes: 21440
N,M = map(int,input().split())
X = list(map(int,input().split()))

from collections import Counter
cs = [Counter() for _ in range(M+1)]
ca = Counter()
for x in X:
    cs[x%M][x] += 1
    ca[x%M] += 1

ans = ca[0]//2
for i in range(1,(M+1)//2):
    j = M-i
    ans += min(ca[i], ca[j])
    if ca[i] > ca[j]:
        d = (ca[i] - ca[j]) // 2
        for v in cs[i].values():
            t = min(d, v//2)
            d -= t
            ans += t
            if d==0: break
    elif ca[i] < ca[j]:
        d = (ca[j] - ca[i]) // 2
        for v in cs[j].values():
            t = min(d, v//2)
            d -= t
            ans += t
            if d==0: break
if M%2==0:
    ans += ca[M//2]//2
print(ans)

Measured memory_bytes: 51184
import java.util.Scanner;

/**
 * Sort
 */
public class Main{

    public static void main(String[] args) {
        int a, b, c;
        Scanner sc = new Scanner(System.in);
        a = sc.nextInt();
        b = sc.nextInt();
        c = sc.nextInt();

        if (a <= b && b <= c) {
            System.out.println(a + " " + b + " " + c);
        } else if (a <= c && c <= b) {
            System.out.println(a + " " + c + " " + b);
        } else if (b <= a && a <= c) {
            System.out.println(b + " " + a + " " + c);
        } else if (b <= c && c <= a) {
            System.out.println(b + " " + c + " " + a);
        } else if (c <= a && a <= c) {
            System.out.println(c + " " + a + " " + b);
        } else {
            System.out.println(c + " " + b + " " + a);
        }

        sc.close();
    }
}


Measured memory_bytes: 26348
import java.util.*;import java.io.*;import java.math.*;
public class Main
{
    public static void process()throws IOException
    {
        int n=ni();
        int k=ni();
        int[]A=nai(n);
        int[]dp=new int[n];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        dp[1]=Math.abs(A[0]-A[1]);
        for(int i=2;i<n;i++)
        {
            for(int j=1;j<=Math.min(i,k);j++)
                dp[i]=Math.min(dp[i-j]+Math.abs(A[i-j]-A[i]),dp[i]);
        }
        pn(dp[n-1]);
    }

    static AnotherReader sc;
    static PrintWriter out;
    public static void main(String[]args)throws IOException
    {
        boolean oj = true;
        if(oj){sc=new AnotherReader();out=new PrintWriter(System.out);}
        else{sc=new AnotherReader(100);out=new PrintWriter("output.txt");}
        int t=1;
        // t=ni();
        while(t-->0) {process();}
        out.flush();out.close();  
    }

    static void pn(Object o){out.println(o);}
    static void p(Object o){out.print(o);}
    static void pni(Object o){out.println(o);out.flush();}
    static int ni()throws IOException{return sc.nextInt();}
    static long nl()throws IOException{return sc.nextLong();}
    static double nd()throws IOException{return sc.nextDouble();}
    static String nln()throws IOException{return sc.nextLine();}
    static int[] nai(int N)throws IOException{int[]A=new int[N];for(int i=0;i!=N;i++){A[i]=ni();}return A;}
    static long[] nal(int N)throws IOException{long[]A=new long[N];for(int i=0;i!=N;i++){A[i]=nl();}return A;}
    static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}

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

    static class AnotherReader{BufferedReader br; StringTokenizer st;
    AnotherReader()throws FileNotFoundException{
    br=new BufferedReader(new InputStreamReader(System.in));}
    AnotherReader(int a)throws FileNotFoundException{
    br = new BufferedReader(new FileReader("input.txt"));}
    String next()throws IOException{
    while (st == null || !st.hasMoreElements()) {try{
    st = new StringTokenizer(br.readLine());}
    catch (IOException  e){ e.printStackTrace(); }}
    return st.nextToken(); } int nextInt() throws IOException{
    return Integer.parseInt(next());}
    long nextLong() throws IOException
    {return Long.parseLong(next());}
    double nextDouble()throws IOException { return Double.parseDouble(next()); }
    String nextLine() throws IOException{ String str = ""; try{
    str = br.readLine();} catch (IOException e){
    e.printStackTrace();} return str;}}
   
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}

Measured memory_bytes: 34572
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define rep(i,n) for (int i=0; i<n;++i)
typedef long long ll;
using namespace std;
int N;
ll W;
ll v[103], w[103];
ll Weight[103][100003]; // nこ目まで考慮して、価値がiの時の重さの最低値
ll INF = 1e18;

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

  cin >> N >> W;
  rep(i, N) {
    cin >> w[i] >> v[i];
    rep(j, 100002) {
      Weight[i+1][j] = INF;
    }
  }

  rep(i, N) {
    rep(j, i*1000+1) { // 0からWまでの価値のrange
      Weight[i+1][j] = min(Weight[i+1][j], Weight[i][j]);
      if (Weight[i][j] + w[i] <= W) Weight[i+1][j+v[i]] = min(Weight[i+1][j+v[i]], Weight[i][j]+w[i]);
    }
  }

  int ans = 0;
  rep(i, N*1000+1) {
    if (Weight[N][i] > 0 && Weight[N][i] <= W) ans = i;
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 79360
#include<stdio.h>
#include<math.h>
#define N 1000

int main(void){
  int i,num,j;
  double x[N],y[N];
  double a,b,c,z,sum,pre;
  char hoge;

  for(i=0;scanf("%lf%c%lf",&x[i],&hoge,&y[i])==3;i++){}
  num=i;
  for(i=0,sum=0.0;i<num-2;i++){
    a=(x[0]-x[i+1])*(x[0]-x[i+1])+(y[0]-y[i+1])*(y[0]-y[i+1]);
    a=sqrt(a);
    b=(x[i+1]-x[i+2])*(x[i+1]-x[i+2])+(y[i+1]-y[i+2])*(y[i+1]-y[i+2]);
    b=sqrt(b);
    c=(x[i+2]-x[0])*(x[i+2]-x[0])+(y[i+2]-y[0])*(y[i+2]-y[0]);
    c=sqrt(c);
    z=(a+b+c)/2.0;
    sum+=sqrt(z*(z-a)*(z-b)*(z-c));
  }
  printf("%0.6f\n",sum);
  return 0;
}

Measured memory_bytes: 0
#include <iostream>

int main()
{
    using namespace std;
    // n個の偶数、m個の奇数
    // gg kk
    int n, m;
    int ans = 0;

    cin >> n;
    cin >> m;
    //cout << n << m << endl;

    // n(n-1) / 2 + m(m-1) /2

    ans = (n * (n - 1) + m * (m - 1)) / 2;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

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

	int count = 0;
	for(int i = 1;i < n-1; ++i){
		if(p[i] < p[i+1] && p[i] > p[i-1]){
			count++;
			continue;
		}

		if(p[i] > p[i+1] && p[i] < p[i-1]){
			count++;
		}
	}

	cout << count << endl;
}

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

#define ll long long
#define vl vector<ll>
#define vvl vector<vector<ll>> //vvl data(10, vector<ll>(10);
#define fo(i,a,b) for(ll i=a; i<b; i++)

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

    if(N[N.size()-1] == '3') cout << "bon" << endl;
    else if(N[N.size()-1] == '0' || N[N.size()-1] == '1' || N[N.size()-1] == '6' || N[N.size()-1] == '8') cout << "pon" << endl;
    else cout << "hon" << endl;

}

/*
　 ◇　　　　 ミ ◇
　◇◇　 /￣|　 ◇◇
◇◇＼　 L＿| ◇◇
　　彡Ｏ(・＿・)/
　 　　ヽ Ｐ`Ｏ
　　 ／彡#_|ミ＼
　　　 </LL凵>
　　　　∪ ∪
pass system test !!
*/

Measured memory_bytes: 3592
#include<iostream>
#include<string>
#include<algorithm>
#include<map>

using namespace std;

typedef long long ll;

int main() {
   int N;
   cin >> N;
   string s;
   map<string, ll> log;
   for (int i = 0; i < N; i++) {
      cin >> s;
      sort(s.begin(), s.end());
      // cout << s << endl;
      log[s]++;
   }
   ll ans = 0;
   for (auto& it : log) {
      if (it.second <= 1) continue;
      ll i = it.second;
      ll tmp2 = i * (i - 1);
      tmp2 /= 2;
      ans += tmp2;
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 11136
n = int(input())


def dsum(n):
    res = 0
    while n > 0:
        res += n % 10
        n //= 10
    return res


min_sum = float('inf')
for a in range(1, n):
    min_sum = min(min_sum, dsum(a) + dsum(n - a))
print(min_sum)


Measured memory_bytes: 2940
#include <stdio.h>

int main(){
	int x=0;
	int h=0;
	int m=0;
	int s=0;
	
	printf("");
	scanf("%d",&x);
	
	while(1){
		if(x>=0 && x<86400){
			break;
		}else{
			printf("");
			scanf("%d",&x);
			continue;
		}
	}
	h=x/3600;
	m=(x-h*3600)/60;
	s=x-h*3600-m*60;
	
	printf("%d:%d:%d\n",h,m,s);
	
	return 0;
}	

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

vector<int> ans;

int main(){
  int n;

  while(cin >> n,n){
    vector<int> val;
    int ans_t=1000001;
    for(int i=0; i<n; ++i){
      int tmp;
      cin >> tmp;
      val.push_back(tmp);
    }
    sort(val.begin(),val.end(),greater<int>());
    for(int i=0; i<n-1; ++i){
      int tmp = val[i]-val[i+1];
      if(ans_t > tmp){
	ans_t = tmp;
      }
    }
    ans_t =abs(ans_t);
    ans.push_back(ans_t);
  }

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

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

#define rep(i,s,n) for(ll i = (s); i < (n); i++)
#define rep0(i,n) rep(i,0,n)
#define rep1(i,n) rep(i,1,n+1)
#define repR(i,s,n) for(ll i = (n-1); i >= (s); i--)
#define repR0(i,n) repR(i,0,n)
#define repR1(i,n) repR(i,1,n+1)

#define BR "\n"
#define SP " "
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << SP; } cout << BR;
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << BR;
#define fcout cout << fixed << setprecision(18)

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

int a[100];
int cells[100][100]; // r * c

int main() {
  ll N , K;
  cin >> N >> K;

  vector<ll> A(N), F(N);
  rep0(i, N) cin >> A[i];
  rep0(i, N) cin >> F[i];

  sort(A.begin(), A.end());
  sort(F.begin(), F.end());
  reverse(F.begin(), F.end());

  ll l = -1, r = 1e12, m;
  while (l + 1 < r) {
    m = (l + r) / 2;
    ll temp = 0;
    rep0(i, N) {
      ll q = m / F[i];
      temp += max(A[i] - q, 0ll);
    }
    // cout << m << SP << temp << BR;
    if (temp <= K) {
      r = m;
    } else {
      l = m;
    }
  }

  cout << r << BR;
  return 0;
}

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

using namespace std;

int change[10][10];
int wall[200][200];
int H, W;
int leastchange[10];

int solve(int cost, int old[10], int num, int first);
int ans = 0;
int main() {
	cin >> H >> W;
	for (int i = 0; i < 10; i++)for (int j = 0; j < 10; j++) cin >> change[i][j];

	for (int i = 0; i < 200; i++)for (int j = 0; j < 200; j++) wall[i][j] = -1;

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

	for (int i = 0; i < 10; i++) {
		leastchange[i] = 9999;
		int temp[10] = { 0 };
		temp[i] = 1;
		solve(0, temp, i, i);
	}

	for (int i = 0; i < H; i++)for (int j = 0; j < W; j++) {
		if (wall[i][j] != -1) {
			ans += leastchange[wall[i][j]];
		}
	}

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

int solve(int cost, int old[10], int num, int first) {
	if (num != 1) {
		for (int i = 0; i < 10; i++) {
			if (!old[i]) {
				int temp[10];
				for (int j = 0; j < 10; j++) temp[j] = old[j];
				temp[i] = 1;
				solve(cost + change[num][i], temp, i, first);
			}
		}
	}
	else {
		if (leastchange[first] > cost) leastchange[first] = cost;
	}
	return 0;
}

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

int main(){
    unsigned int n, y;
    cin >> n >> y;

    for(int i=0;i<=n;i++){
        for(int j=0;j<=n-i;j++){
            if((i*10000 + j*5000 + (n-i-j)*1000) == y){
                cout << i << ' ' << j << ' ' << n-i-j << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;
}


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 = sc.nextInt();
		if (n == 1) {
			System.out.println(1);
		} else if (n % 2 == 0) {
			System.out.println(0.5);
		} else {
			double a = n / 2 + 1;
			System.out.println(a / n);
		}
	}
}


Measured memory_bytes: 22612
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
#define int long
#define ll long long
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) x.size()
#define fi first
#define se second
const int INF = 1e9;
using namespace std;

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

const int MOD = 1000000007;
const int MX = 777777 + 5;
int fac[MX+5],inv[MX+5];

unordered_map<ll,int> prime_factor(ll n){
    unordered_map<ll,int> ret;
    for(ll i=2; i*i<=n; i++){
        while(n % i == 0){
            ret[i]++;
            n /= i;
        }
    }
    if(n != 1) ret[n]=1;
    return ret;
}
 
int power(int x,int y,int p){
	int res=1;
	x=x%p;
	while(y){
		if(y&1)res=(res*x)%p;
		y=y>>1;
		x=(x*x)%p;
	}
	return res;
}
void init(){
  int n=MX+4;
	fac[0] = 1;
  for(int i=0;i<n;++i)fac[i+1]=fac[i]*(i+1)%MOD;
  inv[n]=power(fac[n],MOD-2,MOD);
  for(int i=n-1;i>=0;--i)inv[i]=inv[i+1]*(i+1)%MOD;
}
// nPk = nCk * fac[k]
int comb(int n,int r){return (fac[n]*inv[r])%MOD*inv[n-r]%MOD;}
int H(int n,int r){
  return comb(n+r-1,r)%MOD;
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(20);

    int N,M; cin >> N >> M;
    init();
    int ans=1;
    for(auto a:prime_factor(M)){
        ans=comb(a.se+N-1,a.se)*ans%MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 12416
#include <bits/stdc++.h>
#define ll long long
#define rw freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
#define pb push_back
#define F first
#define S second
#define pf push_front
#define lp(i,a,b) for (int i=a;i<=b;++i)
#define lp2(i,a,b) for (int i=a;i>=b;--i)
#define f(x) return cout<<x<<"\n",0
#define pii pair<int,ll>
#define mod 1000000007
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define p(x) cout<<#x<<" = { "<<x<<" } \n"
#define FAST ios::sync_with_stdio(0),ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N=1e5+4;
ll dp[105][N]= {};
int n;
pii arr[N]= {};
ll solve(int idx,int rem)
{
    if (rem<0)
        return -(int)1e13;
    if (idx>=n)
        return 0;
    ll &ret=dp[idx][rem];
    if (~ret)
        return ret;
    ret=0;
    ret=max(ret,solve(idx+1,rem-arr[idx].F)+arr[idx].S);
    ret=max(ret,solve(idx+1,rem));
    return ret;
}
int main()
{
#ifdef ONLINE_JUDGE
    FAST;
#endif
    memset(dp,-1,sizeof(dp));
    int W;
    cin>>n>>W;
    lp(i,0,n-1) cin>>arr[i].F>>arr[i].S;
    cout<<solve(0,W)<<"\n";
    return 0;
}

Measured memory_bytes: 83840
#include<iostream>
#include<algorithm>
#include<climits>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define scan(arg) cin>>arg
#define prin(arg) cout<<arg<<"\n"
#define prin2(arg1,arg2) cout<<arg1<<" "<<arg2<<"\n"
using namespace std;
typedef long long ll;
const int NMAX=1<<17;

class uft{
public:
  int par[100010];//親
  int rank[100010];//木の深さ
  int size[100010];//木の大きさ
  uft(int N);//コンストラクタ
  int find(int x);
  void unite(int x,int y);
  bool same(int x,int y);
  int usize(int x);
};
uft::uft(int N){//コンストラクタ
  for(int i=0;i<N;i++){
    par[i]=i;
    rank[i]=0;
    size[i]=1;
  }
}
int uft::find(int x){//xの根を返す
  if(par[x]==x) return x;//根の親は自分自身
  else return par[x]=find(par[x]);//再起で親を辿る
}
void uft::unite(int x,int y){//x,yを併合
  x=find(x);
  y=find(y);
  if(x==y) return ;//根が同じなら併合する必要なし

  if(rank[x]<rank[y]){//木の深い方に浅い方をつける
    par[x]=y;
    size[y]+=size[x];
  }
  else{
    par[y]=x;
    size[x]+=size[y];
    if(rank[x]==rank[y]) rank[x]++;//同じ深さなら深さを増やす
  }
}
bool uft::same(int x,int y){//x,yが同じグループにいるかどうかを返す
  return find(x)==find(y);//根が同じかどうかを判断する
}
int uft::usize(int x){
  return size[find(x)];
}


int n,m;
int p[100010];
int x[100010],y[100010];
int main(){
  scan(n);scan(m);
  rep(i,n){
    scan(p[i]);
  }
  rep(i,m){
    scan(x[i]);scan(y[i]);
  }
  uft uf(n);
  rep(i,m){
    uf.unite(x[i]-1,y[i]-1);
  }
  int res=0;
  rep(i,n){
    if(uf.same(i,p[i]-1)){
      res++;
    }
  }
  prin(res);

  
  

  return 0;
}


Measured memory_bytes: 2560
from itertools import accumulate

N, K = map(int, input().split())
S = input()

serial = []
if S[0] == '0':
    serial.append(0)
i = 0
while i < N:
    j = i
    while j < N and S[j] == S[i]:
        j += 1
    serial.append(j - i)
    i = j
if S[-1] == '0':
    serial.append(0)

serial_cumsum = [0]+list(accumulate(serial))
ans = 0
for l in range(0, len(serial_cumsum), 2):
    r = min(len(serial_cumsum) - 1, l + 2*K + 1)
    temp = serial_cumsum[r] - serial_cumsum[l]
    if ans < temp:
        ans = temp
print(ans)

Measured memory_bytes: 8704
s=gets.chomp.split("")
ans = 10**5
h = {}
s.each_with_index do |c, i|
  h[c] = [-1] if !h.has_key?(c)
  h[c] << i
end


ans = 10**5
h.each do |k,v|
  v << s.size
  tmp = 0
  v.each_cons(2) do |a,b|
    tmp = b-a if b-a > tmp
  end
  ans = tmp if ans > tmp
end
puts ans-1

Measured memory_bytes: 2044
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
///////////////////////////////////////

//あらかじめ数xを数yに変換するための最小コストを計算しておく
int main() {
	int H, W;
	int C[10][10], A[202][202];
	cin >> H >> W;
	for (int i = 0; i < 10; ++i) {
		for (int j = 0; j < 10; ++j) {
			cin >> C[i][j];
		}
	}
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			cin >> A[i][j];
		}
	}
	for (int i = 0; i < 10; ++i) {
		for (int j = 0; j < 10; ++j) {
			for (int k = 0; k < 10; ++k) {
				C[j][k]= min(C[j][k], C[j][i] + C[i][k]);
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			if (0 <= A[i][j]) {
				ans += C[A[i][j]][1];
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define zep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(int i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	string s, t;
	cin >> s >> t;
	ll ans = 0;
	zep(i, 0, s.size()){
		if(s[i] != t[i])ans++;
	}
	print(ans)
	
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SZ(x) ((int)(x).size())
using ll = long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 29;
const ll INF64 = 1ll << 45;
const int mod = 1000000007;
//const int mod = 998244353;


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

struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};


int main()
{
  int n;
  cin >> n;
  map<int, int> m;
  for(int i = 2; i <= 100; ++i) m[i] = 0;


  for(int i = 2; i <= n; ++i) {
    int x = i;
    int lim = sqrt(i);
    for(int j = 2; j <= lim; ++j) {
      while(x%j==0) {
        ++m[j];
        x/=j;
      }
    }
    if(x != 1) ++m[x];
  }
  int ans = 0;
  for(int a = 2; a <= n; ++a) {
    for(int b = 2; b <= n; ++b) {
      if(a != b && m[a] >= 2 && m[b] >=24) ++ans; 
    }
  }
  for(int a = 2; a <= n; ++a) {
    for(int b = 2; b <= n; ++b) {
      if(a != b && m[a] >= 4 && m[b] >= 14) ++ans; 
    }
  }
  for(int a = 2; a <= n; ++a) {
    for(int b = 2; b <= n; ++b) {
      for(int c = b+1; c <= n; ++c) {
        if(a != b && a != c && m[a] >= 2 && m[b] >= 4 && m[c] >= 4) ++ans;
      }
    }
  }
  for(int a = 2; a <= n; ++a) if(m[a] >= 74) ++ans;
  cout << ans << endl;
}

Measured memory_bytes: 3700
N=int(input())
dc={}
for i in range(N):
    key=input()
    if key not in dc:
        dc[key]=1
    else:
        dc[key]+=1
max=0
lst=[]
for i in dc:
  if dc[i]>max:
    max=dc[i]
    lst.clear()
    lst.append(i)
  elif dc[i]==max:
    lst.append(i)
lst.sort()
for i in lst:
  print(i)

Measured memory_bytes: 32220
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <cctype>
using namespace std;
int main(){
    double A,B;cin>>A>>B;
    if(A>B){
        puts("GREATER");
    } else if (B>A) {
        puts("LESS");
    } else {
        puts("EQUAL");
    }
}

Measured memory_bytes: 256
n = int(input())
s = input()

min_num = 300000
w_west = 0
e_east = s.count("E")
for s_i in s:
    if s_i == "E":
        e_east -= 1
    else:
        w_west += 1
    tmp = w_west + e_east - bool(s_i == "W")
    if tmp < min_num:
        min_num = tmp
print(min_num)

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

using namespace std;

int main(){
        string s;

        cin >> s;

        if (s == "Sunny"){
                cout << "Cloudy" << endl;
        }
        else if (s == "Cloudy"){
                cout << "Rainy" << endl;
        }
        else if(s == "Rainy" ){
                cout << "Sunny" << endl;
        }
        return 0;
}

Measured memory_bytes: 3560
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long Z = sc.nextInt();
		long W = sc.nextLong();
		long[] a = new long[N];
		for(int i=0; i<N; i++) {
			a[i] = sc.nextLong();
		}
		if(N==1) {
			System.out.println(Math.abs(a[N-1]-W));
		} else {
			System.out.println(Math.max(Math.abs(a[N-1]-a[N-2]), Math.abs(a[N-1]-W)));	
		}
	}
	
	static int binarySearch(int[] A, int x) {
		int l = 0;
		int r = A.length;
		while(l<r) {
			int mid = (l+r)/2;
			if(A[mid] == x) return mid;
			else if(x<A[mid]) r = mid;
			else l = mid+1;
		}
		return -1;
	}
	
	static long upper_bound(int[] A, int b) {
		// bよりおおきい値がはじめて出てくるindexを返す
		return lower_bound(A, b+1);
	}

	static long lower_bound(int[] A, int b) {
		// b以上の値がはじめて出てくるindexを返す
		int lb=0;
		int ub=A.length;
		while(ub>lb) {
			int mid = (lb+ub)/2;
			if(A[mid]>=b) ub = mid;
			else lb = mid+1;
		}
		return lb;
	}
	
	// union find lib
	// usage:
	// 最初にinitを呼ぶ
	// root: 直接は呼ばないで
	// unite: まとめる
	// same: グループ判定
	static void init(int par[], int N) {
		for(int i=0; i<N; i++) {
			par[i] = i;
		}
	}
	
	static int root(int x, int [] par) {
		if(par[x] == x) {
			return x;
		} else {
			return (par[x] = root(par[x], par));
		}
	}
	
	static boolean same(int x, int y, int[] par) {
		return root(x, par) == root(y, par);
	}
	
	static void unite(int x, int y, int[] par) {
		x = root(x, par);
		y = root(y, par);
		if(x == y) return;
		par[x] = y;
	}
	
	// end union find lib
	
	// number lib
	
	static int max(int...ls) {
		int ans = Integer.MIN_VALUE;
		for(int i=0; i<ls.length; i++) {
			ans = Math.max(ans, ls[i]);
		}
		return ans;
	}
	
	static int min(int...ls) {
		int ans = Integer.MAX_VALUE;
		for(int i=0; i<ls.length; i++) {
			ans = Math.min(ans, ls[i]);
		}
		return ans;
	}
	
	static long lcm(long a, long b) {
		return a*(b/gcd(a, b));
	}
	
	static long gcd(long a, long b) {
		long ta = Math.max(a, b);
		long tb = Math.min(a, b);
		long tmp;
		while((tmp = ta%tb) != 0) {
			ta = tb;
			tb = tmp;
		}
		return tb;
	}
	
	static long modcomb(long n, long k, long mod) {
		if(k==1) {
			return n;
		}
		
		long ans = 1;
		for(long i=n; i>=n-k+1; i--) {
			ans = (ans * i)%mod;
		}
		for(long i=k; 0<i; i--) {
			ans = (ans * modpow(i, mod-2, mod)) % mod;
		}
		return ans;
	}
	
	static long modpow(long a, long b, long mod) {
		if(b==0) return 1;
		if(b%2==0) {
			long d = modpow(a, b/2, mod);
			return (d*d)%mod;
		} else {
			return (a*modpow(a, b-1, mod))%mod;
		}
	}
	
	static int disit(long a, long d) {
		int count = 0;
		while(a!=0) {
			a = a/d;
			count++;
		}
		return count;
	}
	
	// end number lib
}

Measured memory_bytes: 25324
#include <iostream>
#include <queue>

typedef std::pair<int, int> P; //(x,y)
typedef std::pair<P, P> PP;
typedef std::pair<PP, int> D;

int x, y;
int map[51][51];
bool visit[51][51][51][51];

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

bool back(P p){
	if(map[p.second][p.first])return true;
	else if(p.second < 0 || p.second >= y || p.first < 0 || p.first >= x)return true;
	else return false;
}

int main(){
	while(true){
		for(int i = 0; i < 51; ++i)for(int j = 0; j < 51; ++j)for(int k = 0; k < 51; ++k)for(int l = 0; l < 51; ++l)visit[i][j][k][l] = false;
		
		std::cin >> x >> y;
		if(x == 0 && y == 0)break;
		
		P t, k;
		std::cin >> t.first >> t.second;
		std::cin >> k.first >> k.second;
		--t.first, --t.second;
		--k.first, --k.second;

		for(int i = 0; i < y; ++i){
			for(int j = 0; j < x; ++j){
				std::cin >> map[i][j];
			}
		}

		bool f = false;

		std::queue<D> que;
		que.push(D(PP(t, k), 0));
		
		visit[t.first][t.second][k.first][k.second] = true;

		while(!que.empty()){
			D d = que.front();
			que.pop();
			
			P ct = d.first.first, ck = d.first.second;
			
			if(d.second >= 100){
				break;
			}
			if(ct == ck){
				f = true;
				std::cout << d.second << std::endl;
				break;
			}
			
			for(int i = 0; i < 4; ++i){
				P nt = ct, nk = ck;
				nt.first += dx[i]; nt.second += dy[i];
				nk.first -= dx[i]; nk.second -= dy[i];
				
				if(back(nt))nt = ct;
				if(back(nk))nk = ck;
				
				if(!visit[nt.first][nt.second][nk.first][nk.second]){
					visit[nt.first][nt.second][nk.first][nk.second] = true;	
					que.push(D(PP(nt, nk), d.second + 1));
				}
			}
		}
		
		if(!f)std::cout << "NA" << std::endl;
	}
	return 0;
}

Measured memory_bytes: 7996
#include <iostream>
using namespace std;
int main() {
  int N,K; cin>>N>>K; N--;
  for(int i=0; i<K; i++) {
    int x, y; cin >> x >> y;
    x --, y --;
    if(N/2<x) x = N-x;
    if(N/2<y) y = N-y;
    cout << (min(x,y))%3+1 << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
long mod=1e9+7,dp[5005][5005],ans;
s[5005];
main(N,M)
{
	scanf("%d%s",&N,s);
	M=strlen(s);
	dp[0][0]=1;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<=5000;j++)
		{
			dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j]*2)%mod;
			dp[i+1][j?j-1:0]=(dp[i+1][j?j-1:0]+dp[i][j])%mod;
		}
	}
	ans=dp[N][M];
	for(int i=0;i<M;i++)ans=ans*(mod+1)/2%mod;
	printf("%d\n",ans);
}

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

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,n) for(int i=1;i<=(int)(n);i++)
#define rep3(i,n) for(int i=0;i<=(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
#define repll(i,n) for(ll i=0;i<(ll)(n);i++)
#define repll2(i,n) for(ll i=1;i<=(ll)(n);i++)
#define REPLL(i,m,n) for(ll i=m;i<(ll)(n);i++)
#define INF (int)1e9  //
#define LINF (ll)4e18  //
#define MOD (int)(1e9)+7
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define PI 3.1415926535898

//------------------------------------------------------

int main() {
    ll n, m;
    cin >> n >> m;
    if (n >= m / 2) cout << m / 2 << endl;
    else {
        ll cp = m / 2 - n;
        cout << n + cp / 2 << endl;
    }

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int N;
	cin >> N;
	cout << N * N << endl;



	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std; inline void fileio(const char* in, const char* out) { freopen(in, "r", stdin); freopen(out, "w", stdout); } 
#define TD typedef
#define forx(i,n) for(int i = 0; i < (n); ++i)
TD long long ll; TD long double ld; TD pair<int,int> pii; TD pair<ll, ll> pll; TD vector<int> VI; TD vector<bool> VB; TD vector<ll> VL;
const char nl = '\n'; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fll; const ld EPS = 1e-9, PI = acos(-1);
#define ff first
#define ss second

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  // Emily <3
  int n, k;
  cin >> n >> k;
  VI heights(n);
  forx(i,n) cin >> heights[i];
  VI cost(n, INF); // cost[i] is min cost to reach i
  cost[0] = 0;
  for(int i = 1; i < n; ++i) {
    for(int j = 1; j <= k; ++j) {
      int o = i-j;
      if (o >= 0) {
        cost[i] = min(cost[i], cost[o] + abs(heights[o] - heights[i]));
      }
    }
  }
  cout << cost[n-1];
  
  cerr << "Time: " << (ld)clock() / CLOCKS_PER_SEC << nl;
  return 0;
}



Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <iomanip>
#include <unordered_map>

using namespace std;
typedef long long  ll;

int main()
{
	vector<string> str(3);
	cin >> str[0] >> str[1] >> str[2];
	ll player = 0;
	ll num[3] = { 0, 0, 0 };
	for (ll i = 0; i < 300; i++)
	{
		num[player]++;
		if (num[player] == str[player].length() + 1) break;
		switch (str[player][num[player] - 1])
		{
		case 'a':
			player = 0;
			break;
		case 'b':
			player = 1;
			break;
		case 'c':
			player = 2;
			break;
		default:
			break;
		}
	}
	switch (player)
	{
	case 0:
		cout << 'A' << endl;
		break;
	case 1:
		cout << 'B' << endl;
		break;
	case 2:
		cout << 'C' << endl;
		break;
	default:
		break;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 using namespace std;
 int main() {
 long long A, B;
 cin >> A >> B;
 if(A % 2 != B % 2) {
 cout << "IMPOSSIBLE" << endl;
 } else {
 cout << (A + B) / 2 << endl;
 }
 return 0;
 }

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

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int state = 0;
    int ans = 0;
    for(int i=0; i<n; i++){
        if(state==0){
            if(s[i]=='A'){
                state++;
            }
            else state=0;
        }
        else if(state==1){
            if(s[i]=='B'){
                state++;
            }
            else if(s[i]=='A'){
            }
            else state=0;
        }
        else if(state==2){
            if(s[i]=='C'){
                ans++;
                state=0;
            }
            else if(s[i]=='A'){
                state=1;
            }
            else if(s[i]=='B'){
                state=0;
            }
            else state=0;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256