akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;

int main(){
    int n,L[36]={},l,S[36]={},c = 0;
    char m,M[36]={},T[36]={},e,f;
    cin >> n;

    for (int i = 0; i < n; i ++){
        cin >> m >> l;
        M[i] = m;
        T[i] = m; 
        L[i] = l;
        S[i] = l;
    }

    for (int i = 0; i < n; i++){
        for (int j = n-1; i < j; j--){
            if (L[j] < L[j-1]){
                int a = L[j-1];
                L[j-1] = L[j];
                L[j] = a;
                
                char b = M[j-1];
                M[j-1] = M[j];
                M[j] = b;
            }
        }
    }

    for (int i = 0; i < n; i++){ 
        if (i == n-1){
            cout << M[i] << L[i] << '\n';
        }
        else{
            cout << M[i] << L[i] << " ";
        }
    }
    cout << "Stable" << '\n'; 

    for (int i = 0; i < n; i++){
        int minj = i;
        for (int j = i; j < n; j++){
            if (S[j] < S[minj]){
                minj = j;
            }
        }
        int c = S[i];
        S[i] = S[minj];
        S[minj] = c;

        char d = T[i];
        T[i] = T[minj];
        T[minj] = d;
    }

    for (int i = 0; i < n; i++){
        if (i == n-1){
            cout << T[i] << S[i] << '\n';
        }
        else{
            cout << T[i] << S[i] << " ";
        }
    }
    for (int i = 0; i < n; i++){
        if (M[i] != T[i]){
            c += 1;
        }
    }
    if (c > 0){
        cout << "Not stable" << '\n';
    }
    else {
        cout << "Stable" << '\n';
    }
    return 0;
}


Measured memory_bytes: 3088
x=int(input())
n=10**5
import math
def eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
q=eratosthenes(n)

ans=[0]*(10**5+1)
for i in range(10**5):
    ans[i+1]=ans[i]+(1 if i+1 in q and (i+1+1)//2 in q else 0 )
for i in range(x):
    l,r = map(int,input().split())	
    print(ans[r]-ans[l-1])

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())

using namespace std;

using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
template <typename T, typename S> istream& operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
template <typename T, typename S> ostream& operator<<(ostream &os, pair<T, S> &p) { cout << p.first << ' ' << p.second; return os; }

void solve() {
  string s; cin >> s;
  int n = s.size();
  int ans = 0;
  rep(i, (n + 1) / 2) if (s[i] == 'p') ans--;
  repi(i, (n + 1) / 2, n) if (s[i] == 'g') ans++;
  cout << ans << '\n';
}


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



const int N = 107;

int arr[N];
int n;
int minimumVal = 1e5 + 7;

int dp[100007][2];
int solve(int rem, bool turn) {
	if (rem < minimumVal) {
		return !turn;
	}

	if (dp[rem][turn] != -1)
		return dp[rem][turn];

	if (turn) {
		int ans = 0;
		for (int i = 0; i < n; i++) {
			if (arr[i] <= rem) {
				ans = max(ans, solve(rem - arr[i], !turn));
			}
		}
		return dp[rem][turn] = ans;
	}
	else {
		int ans = 1;
		for (int i = 0; i < n; i++) {
			if (arr[i] <= rem) {
				ans = min(ans, solve(rem - arr[i], !turn));
			}
		}
		return dp[rem][turn] = ans;
	}
}





int main() {
	cin >> n;
	int k;
	cin >> k;
	memset(dp, -1, sizeof dp);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		minimumVal = min(minimumVal, arr[i]);
	}
	if (!solve(k, 0)) {
		cout << "First";
	}
	else {
		cout << "Second";
	}
}

Measured memory_bytes: 7296
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(int)(a); i!=(int)(b); i++)
#define RFOR(i, a, b) for(int i=(int)(a); i!=(int)(b); i--)
#define REP(i, n) FOR(i, 0, n)
using namespace std;
using ll = long long;

ll calc(vector<ll> a, vector<ll> b, int n){
  vector<ll> c(n);

  if (n % 2 == 0){
    for(int i=0, j=0, k=0; i<n/2; i++){
      c[2*i] = b[j++];
      c[2*i+1] = a[k++];
    }
  }
  else{
    if(a.size() < b.size()) swap(a, b);

    if(a[0] < b[0]) swap(a[0], a[n/2-1]);
    else swap(a[1], a[n/2]);

    for(int i=0, j=0, k=0; i<n; i++){
      if(i % 2){
        c[i] = b[j++];
      }
      else{
        c[i] = a[k++];
      }
    }
  }

  ll ans = 0;
  REP(i, n-1) ans += abs(c[i+1]-c[i]);

  return ans;
}

int main(){
  int n; cin >> n;
  ll a[n];
  REP(i, n) cin >> a[i];

  sort(a, a+n);

  int b = n/2;

  vector<ll> x, y;
  for(int i=0; i<n; i++){
    if(i < b){
      x.push_back(a[i]);
    }
    else{
      y.push_back(a[i]);
    }
  }

  ll ans = calc(x, y, n);

  if(n % 2 == 0){
    cout << ans << endl;
    return 0;
  }

  x.clear(); y.clear();
  for(int i=0; i<n; i++){
    if(i <= b){
      x.push_back(a[i]);
    }
    else{
      y.push_back(a[i]);
    }
  }

  cout << max(calc(x, y, n), ans)<< endl;

  return 0;
}


Measured memory_bytes: 3448
#include<bits/stdc++.h>
#include<vector>
using namespace std;
int main(void){

while(true){
//入力
  int n, m;    cin >> n >> m;
  if(n == 0 && m == 0)  break;

  vector<int> Taro(n), Hanako(m);
  long sum_taro = 0, sum_hanako = 0;
  for(int i = 0 ; i < n ; i++){
    cin >> Taro[i];
    sum_taro += Taro[i];
  }
  for(int i = 0 ; i < m ; i++){
    cin >> Hanako[i];
    sum_hanako += Hanako[i];
  }

//和の比較と合計値の一致をみる(全パターン見る)
  int ans_taro = 0, ans_hanako = 0, ans_sum = 100000;
  for(int i = 0 ; i < n ; i++){
    for(int j = 0 ; j < m ; j++){
      if(sum_taro -Taro[i] + Hanako[j] == sum_hanako -Hanako[j] + Taro[i]){
        if(Taro[i] + Hanako[j] < ans_sum){
          ans_taro = Taro[i];
          ans_hanako = Hanako[j];
          ans_sum = Taro[i] + Hanako[j];
        }
      }
    }
  }

  if(ans_sum == 100000)
    cout << -1 << endl;
  else
    cout << ans_taro << " " << ans_hanako <<endl;
  }

  return 0;
}


Measured memory_bytes: 3096
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for (int i = 0; i < 4; i++) {
			int t = sc.nextInt();
			int n = sc.nextInt();
			if (t == 1) {
				System.out.println(n * 6000);
			} else if (t == 2) {
				System.out.println(n * 4000);
			} else if (t == 3) {
				System.out.println(n * 3000);
			} else {
				System.out.println(n * 2000);
			}
		}
		sc.close();
	}
}

Measured memory_bytes: 26404
let lcs (x, y) =
  let n = String.length x in
  let m = String.length y in
  let dp = Array.make_matrix (n + 1) (m + 1) 0 in
  for i = 1 to n do
    for j = 1 to m do
      dp.(i).(j) <-
        if x.[i-1] = y.[j-1] then dp.(i-1).(j-1) + 1
        else
          let a = dp.(i-1).(j) in
          let b = dp.(i).(j-1) in
          if a > b then a else b;
    done
  done;
  dp.(n).(m)

let () =
  let q = read_int () in
  for _ = 0 to q - 1 do
    Scanf.scanf "%s\n%s\n" (fun x y -> (x, y))
    |> lcs
    |> Printf.printf "%d\n"
  done

Measured memory_bytes: 18588
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
int main(){
    int n,a;
    cin>>n>>a;
    int amari=n%500;
    if(amari<=a)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
#include<cassert>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=500000004;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
int A[110000];
int B[110000];
int C[110000];
struct wolf{
	int a,b,c;
	wolf(){}
};
inline bool operator<(const wolf&a,const wolf&b){
	return a.a*b.b<a.b*b.a;
}
wolf p[110000];
pair<double,int> t[110000];
int n;
int bit[110000];
void add(int a,int b){
	for(;a<110000;a|=a+1)bit[a]+=b;
}
int sum(int a,int b){
	if(a)return sum(0,b)-sum(0,a-1);
	int ret=0;
	for(;b>=0;b=(b&(b+1))-1)ret+=bit[b];
	return ret;
}
long long chk(){
	for(int i=0;i<110000;i++)bit[i]=0;
	long long ret=0;
	for(int i=0;i<n;i++){
		ret+=sum(t[i].second,n-1);
		add(t[i].second,1);
	}
	return ret;
}
int main(){
	int a;scanf("%d",&a);n=a;
	for(int i=0;i<a;i++){
		scanf("%d%d%d",A+i,B+i,C+i);	
	}
	for(int I=0;I<2;I++){
		for(int i=0;i<a;i++){
			if(B[i]<0){
				A[i]=-A[i];
				B[i]=-B[i];
				C[i]=-C[i];
			}
		}
		for(int i=0;i<a;i++){
			p[i].a=A[i];
			p[i].b=B[i];
			p[i].c=C[i];
		}
		long long T=(long long)a*(a-1)/2;
		long long S=(T+1)/2;
 
		std::sort(p,p+a);
		double left=-mod;
		double right=mod;
		for(int i=0;i<70;i++){
			double M=(left+right)/2;
			for(int j=0;j<a;j++){
				t[j]=make_pair((p[j].c-p[j].a*M)/p[j].b,j);
			}
			std::sort(t,t+a);
			long long cnt=chk();
			if(cnt>=S){
				right=M;
			}else left=M;
		}
		printf("%.12f ",left);
		for(int i=0;i<a;i++){
			swap(A[i],B[i]);
		}
	}
}

Measured memory_bytes: 3456
#include <bits/stdc++.h>                                           
 
#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb; 
typedef long long ll;  
typedef double db;                         
 
 
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const int inf = 1e9, N = 3e5 + 48, mod = 1e9 + 7;
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;
 

int n, m, a[90][90], b[90][90], c[90][90];
bitset < 80 * 160 + 21 > dp[90][90]; 

main () {
	cin >> n >> m;
	forn (i, 1, n)
		forn (j, 1, m)
			cin >> a[i][j];


	forn (i, 1, n)
		forn (j, 1, m) {
			cin >> b[i][j]; 
			c[i][j] = abs(a[i][j] - b[i][j]);
		}

	dp[1][1][c[1][1] + 81*81] = 1;
	dp[1][1][81 * 81 - c[1][1]] = 1;
	forn (i, 1, n)
		forn (j, 1, m) {
			if (i < n) {
				dp[i + 1][j] |= (dp[i][j] << c[i + 1][j]); 
				dp[i + 1][j] |= (dp[i][j] >> c[i + 1][j]);
			}
			if (j < m) {
				dp[i][j + 1] |= (dp[i][j] << c[i][j + 1]); 
				dp[i][j + 1] |= (dp[i][j] >> c[i][j + 1]);			
			}
		}

				
	int ans = inf;
	for (int x = dp[n][m]._Find_first(); x < sz(dp[n][m]); x = dp[n][m]._Find_next(x))
		ans = min(ans, abs(x - 81*81));		

	cout << ans << endl;
} 

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

int main() {

  long W, H, x, y;
  cin >> W >> H >> x >> y;

  int f = 0;

  if (double(x) == (double(W) / 2) && double(y) == (double(H) / 2)) {
    f = 1;
  }

  cout << fixed << setprecision(15);
  cout << double(W) * double(H) / 2.0 << " " << f << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
using namespace std;
typedef long long ll;

const int INF = 1e9;

int main(){

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

    int a[m], b[m];
    // cout << n << " " << m << endl;
    for(int i=0; i<m; i++){
        cin >> a[i] >> b[i];
    }
    for(int i=0; i<m; i++){
        a[i] -= 1;
        b[i] -= 1;
    }

    vector<int> v[n];
    for(int i=0; i<m; i++){
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
    }

    queue<int> q;
    q.push(0);
    int d[n];
    fill(d, d+n, INF);
    d[0] = 0;
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i=0; i<v[now].size(); i++){
            int next = v[now][i];
            if(d[next] == INF){
                d[next] = d[now] + 1;
                q.push(next);
            }
        }
    }

    if(d[n-1] == 2){
        cout << "POSSIBLE";
    }
    else{
        cout << "IMPOSSIBLE";
    }


    return 0;
}

Measured memory_bytes: 14704
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> P;

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

  ll f_n=0,n=1;
  char c=s[0];
  ll ans=0;
  for (int i=1; i<s.size(); i++) {
    if (s[i]!=s[i-1]) {
      ans+=n/2;
      if (f_n==0) {
	f_n=n;
      }
      n=1;
    }
    else {
      n++;
    }
  }
  if (f_n==0) {
    cout<<k*s.size()/2<<endl;
    return 0;
  }
  ans+=n/2;
  ans=ans*k;
  if (f_n%2==1&&n%2==1&&s[0]==s[s.size()-1]) {
    ans+=k-1;
  }
  cout<<ans<<endl;
  return 0;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  int a, b, c;
  cin >> a >> b >> c;
  if ((c >= a) && (c <= b)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

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

t_max = -1
t_i = 0
a_max = -1
a_i = 0
ans = 1
mod = 10 ** 9 + 7

for i in range(N):
    t = t_list[i]
    a = a_list[i]
    if t > t_max:
        t_max = t
        t_i = i
    if a >= a_max:
        a_max = a
        a_i = i
if a_max == t_max and t_i <= a_i:
    prev_a = a_list[-1]
    prev_t = t_list[0]
    for i in range(1, t_i):
        t = t_list[i]
        if t == prev_t:
            ans *= prev_t
            ans %= mod
        prev_t = t
    for i in range(N-2, t_i, -1):
        a = a_list[i]
        if a == prev_a:
            ans *= prev_a
            ans %= mod
        prev_a = a
    print(ans % mod)
else:
    print(0)


Measured memory_bytes: 18756
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod=1e9+7;

int main(){
    int flag = 0;
    string s;
    cin >> s;
    if(s[0]=='A' && s[1] >= 'a' && s[1] <= 'z' && s[s.length()-1] >='a' && s[s.length()-1] <= 'z'){
        for(int i=2; i<s.length()-1;i++){
            if(s[i]=='C'){
                flag ++;
            }else if(s[i] < 'a' | s[i] > 'z'){
                flag = 3;
                break;
            }
        }
    }

    if(flag==1){
        cout << "AC" << endl;
    }else{
        cout << "WA" << endl;
    }
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    // Your code here!
    int a, b, i;
    char c, s[100];
    
    scanf("%d%d",&a,&b);
    
    if(a>=b){
        c=b+'0';
        for(i=0;i<a;i++) s[i]=c;
        s[i]='\0';
    }
    
    else{
        c=a+'0';
        for(i=0;i<b;i++) s[i]=c;
        s[i]='\0';
    }
    
    printf("%s\n", s);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
const long long mod = pow(10, 9) + 7;
const long long INF = 1LL << 60;
template <class T> bool chmin(T& a, T b){if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b){if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, int B) {return (A + (B - 1)) / B;}
long long divCeil(int A, long long B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, long long B) {return (A + (B - 1)) / B;}

int main()
{
  int N, T;
  cin >> N >> T;
  
  int min_c = 100000;
  for (int i = 0; i < N; i++)
  {
    int c, t;
    cin >> c >> t;
    if (t <= T) chmin(min_c, c);
  }
  
  if (min_c < 100000) cout << min_c << endl;
  else cout << "TLE" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <set>
using namespace std;
using pii = pair<int,int>;
using pll = pair<long long, long long>;
const long long INF = 1<<29;

const int MOD = 1000000007;
long long ruizyou(long long m,long long n){
  if(m == 0)return 0;
  if(m == 1)return 1;
  long long ans = 1;
  long long tmp = m;
  for(int i=0;i<=30;i++){
    if(n & (1<<i)){
      ans *= tmp;
      ans %= MOD;
    }
    tmp *= tmp;
    tmp %= MOD;
  }
  return ans;
}
long long kaizyou(long long x){
  if(x == 0)return 1;
  return x * kaizyou(x-1) % MOD;
}
long long comb(long long x,long long y){
  long long bunsi = kaizyou(x);
  long long bunbo = kaizyou(x-y) * kaizyou(y) % MOD;
  return bunsi * ruizyou(bunbo,MOD-2) % MOD;
}
struct unionfind{
  vector<int> par;
  vector<vector<int>> children;
  vector<int> hukasa;
  vector<int> kazu;
  unionfind(int n){
    par = vector<int>(n);
    hukasa = vector<int>(n,0);
    kazu = vector<int>(n,1);
    for(int i=0;i<n;i++){
      par.at(i) = i;
    }
  }
  int root(int x){
    if(par.at(x) == x)return x;
    return root(par.at(x));
  }
  void unite(int x,int y){
    int rx = root(x);
    int ry = root(y);
    if(rx == ry)return;
    if(hukasa.at(rx) >= hukasa.at(ry)){
      par.at(ry) = rx;
      hukasa.at(rx) = max(hukasa.at(ry) + 1,hukasa.at(rx));
      kazu.at(rx) += kazu.at(ry);
    }
    else{
      par.at(rx) = ry;
      kazu.at(ry) += kazu.at(rx);
    }
  }
  void newkazu(){
    int n = kazu.size();
    for(int i=0;i<n;i++){
      kazu.at(i) = kazu.at(root(i));
    }
  }
  bool same(int x,int y){
    return root(x) == root(y);
  }
};
int ctoi(char a){
  return a - '0';
}
long long gcd(long long a,long long b){
  long long c = max(a,b);
  long long d = min(a,b);
  if(d % c == 0)return c;
  return gcd(c,d%c);
}
long long lcm(long long a,long long b){
  return a * b / gcd(a,b);
}
void hukasa(vector<vector<int>> s,vector<vector<int>> table,int &ans,pii frm,int n,int m){
  int x,y;
  tie(x,y) = frm;
  set<pii> se;
  if(x-1 >= 0)se.insert(pii(x-1,y));
  if(x+1 < n)se.insert(pii(x+1,y));
  if(y-1 >= 0)se.insert(pii(x,y-1));
  if(y+1 < m)se.insert(pii(x,y+1));
  for(auto t:se){
    int tx,ty;
    tie(tx,ty) = t;
    if(s.at(tx).at(ty) && table.at(tx).at(ty) == -1){
      table.at(tx).at(ty) = table.at(x).at(y) + 1;
      ans = max(ans,table.at(tx).at(ty));
      hukasa(s,table,ans,t,n,m);
      table.at(tx).at(ty) = -1;
    }
  }
}
void daiku(int frm,vector<vector<pii>> g,vector<int> &cost,int n){
  priority_queue<pii,vector<pii>,greater<pii>> q;
  q.push(pii(cost.at(frm),frm));
  vector<bool> kakutei(n,false);
  while(!q.empty()){
    pii now = q.top();
    q.pop();
    int n1,n2;
    tie(n1,n2) = now;
    if(kakutei.at(n2))continue;
    kakutei.at(n2) = true;
    for(auto t:g.at(n2)){
      int tx,ty;
      tie(tx,ty) = t;
      if(cost.at(tx) > n1 + ty){
        cost.at(tx) = n1 + ty;
        q.push(pii(cost.at(tx),tx));
      }
    }
  }
}

int main(){
  long long a,b,c,d;
  cin >> a >> b >> c >> d;
  long long ans = a * c;
  ans = max(ans,a * d);
  ans = max(ans,b * c);
  ans = max(ans,b * d);
  cout << ans << endl;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  for(int i = 0; i < n; i++) cin >> v[i];
  int ans = 0;
  for(int i = 0, c; i < n; i++) {
    cin >> c;
    ans += max(0, v[i]-c);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
pair<long long, long long> p[101];
long long dp[101][100001];

int main() {
	int n, W;
    cin >> n >> W;
    for(int i = 0; i < n; i++)
       cin >> p[i].first >> p[i].second;
    
    memset(dp, 0x3f3f3f3f , sizeof dp);
    for(int i = 0; i < n; i++) dp[i][0] = 0;
    dp[0][p[0].second]=p[0].first;
    for(int j = 1; j < n; j++){
       for(int i = 0; i < 100001; i++){
           dp[j][i] = dp[j-1][i];
            if(i - p[j].second>= 0)
              dp[j][i] = min(dp[j][i], dp[j-1][i - p[j].second] + p[j].first);
       }
    }
    int ans = 0;
    for(int i = 0; i < 100001; i++)
      if(dp[n-1][i] <= W) ans = i;
    cout << ans;
	return 0;
}

Measured memory_bytes: 79104
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,q;
    while(cin>>n>>q,n){
        int m;
        int date[101]={};
        int scan;
        int qmx=0;
        for(int i=0;i<n;i++){
            cin>>m;
            for(int j=0;j<m;j++){
                cin>>scan;
                date[scan]++;
                qmx=max(date[scan],qmx);
            }
        }
        int ans;
        for(int i=0;i<101;i++){
            if(date[i]==qmx){
                ans=i;
                break;
                
            }
            
        }
        if(qmx<q){ans=0;}
        cout<<ans<<endl;
    }
}



Measured memory_bytes: 3076
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;

int main(){
    string s; cin >> s;
    if(s == "Sunny")cout << "Cloudy" << endl;
    if(s == "Cloudy")cout << "Rainy" << endl;
    if(s == "Rainy")cout << "Sunny" << endl; return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define bg begin()
#define en end()

#define pr_arr(name, a, b) \
  for (int i = (a); i < (b); i++) { \
    for (int j = (a); j < (b); j++) {\
      if (j > (a)) printf(" "); \
      printf("%lld", name[i][j]); \
    }\
    printf("\n");\
  }\

using namespace std;

typedef long long ll;

int ans;
char S[55], T[55];

int main(void) {
    scanf("%s", S);
    scanf("%s", T);

    int s_n = strlen(S);
    int t_n = strlen(T);

    int p = -1;
    
    for(int i = s_n - t_n; i >= 0; i--) {
        bool ok = true;
        for(int j = 0; j < t_n; j++) {
            if (S[i+j] != '?' && S[i+j] != T[j]) ok = false;;
        }
        if(ok) {
            p = i;
            break;
        }
    }
    if (p == -1) {
        puts("UNRESTORABLE");
        return 0;
    }

    rep(i, 0, t_n) S[p+i] = T[i];
    rep(i, 0, s_n) {
        if (S[i] == '?') S[i] = 'a';
    }
    printf("%s\n", S);

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll MOD = 1e9+7;

#define vec vector<int>
#define vecll vector<ll>
#define vpair vector<pair<int, int>>
#define vpairll vector<pair<ll, ll>>

#define rep(i,n)         for(int i=(int)0; i<(int)n; i++)
#define REP(i,m,n)       for(int i=(int)m; i<(int)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define prt(var)         cout << var << endl
#define prtd(n, var)     cout << fixed << setprecision(n) << var << endl
#define prt2(v1, v2)     cout << v1 << " " << v2 << endl
#define prt3(v1, v2, v3) cout << v1 << " " << v2 << " " << v3 << endl
#define prtall(var)      rep(i,var.size()){cout << var[i] << " ";} cout << endl

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

int main(void) {
  int n;
  cin >> n;
  if(n%2==0){
    prt(n/2);
  } else {
    prt(n/2+1);
  }
}


Measured memory_bytes: 256
// https://atcoder.jp/contests/abc125/tasks/abc125_d

#include <bits/stdc++.h>
#define REP(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define REPR(i, n) for (int(i) = (n); (i) >= 0; (i)--)
#define FOR(i, m, n) for (int(i) = (m); (i) < (n); i++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int main()
{
  ll N, t, minimize = INF, score = 0;
  bool mcnt = false;
  vector<ll> A(1e5);
  cin >> N;

  REP(i, N)
  {
    cin >> t;
    if (t < 0)
      mcnt = !mcnt;
    t = abs(t);
    score += t;
    minimize = min(minimize, t);
  }

  if (mcnt)
    score -= 2 * minimize;

  cout << score << '\n';

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;
 
using namespace std;
using Graph = vector<vector<Int>>;
 
const double pi = M_PI;
const Int MOD = 1000000007;
 
vector<Int> divisor(Int n) {
    vector<Int> ret;
    for (Int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n)
                ret.push_back(n / i);
        }
    }
    sort(begin(ret), end(ret));
    return ret;
}
 
int main() {
    Int n;
    cin >> n;
 
    vector<Int> n_div(divisor(n)), niti_div(divisor(n - 1));
    n_div.push_back(n);
    niti_div.push_back(n - 1);
 
    Int ans = (Int)niti_div.size();
    Int ro = (Int)n_div.size();
    for (Int i = 0; i < ro; i++) {
        Int nn = n;
        while (nn % n_div[i] == 0 && nn != 0) {
            nn = nn / n_div[i];
        }
 
        if (nn % n_div[i] == 1) {
            ans++;
        }
    }
 
    if (n == 2) {
        ans--;
    }
 
    cout << ans << endl;
 
    return 0;
}

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

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    from collections import Counter

    n = int(input())
    a = [0] * n
    count = 0

    for i in range(n):
        a[i] = int(input())

    for key, value in Counter(a).items():
        if value % 2 != 0:
            count += 1

    print(count)


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

arr=[[False]*3 for _ in range(3)]

for x in b:
  for i in range(3):
    for j in range(3):
      if x==a[i][j]:
        arr[i][j]=True

for i in range(3):
  if all(arr[i]) or all([arr[j][i] for j in range(3)]):
    print('Yes')
    exit()
if all([arr[i][i] for i in range(3)]) or all([arr[i][2-i] for i in range(3)]):
  print('Yes')
  exit()
print('No')

Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define REP(i, n) for (long long i = 0; i < (long long)n; i++)
//#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Vl = vector<ll>;
using vi = vector<int>;
using Graph = vector<vi>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(15); //"for float-base
  // problem"
  int H, W, C = 0;
  cin >> H >> W;
  vector<string> table(H);
  REP(i, H) {
    cin >> table.at(i);
    for (auto x : table.at(i))
      if (x == '#') C++;
  }
  if (C != (H - 1) + (W - 1) + 1) {
    cout << "Impossible" << endl;
    return 0;
  }
  int h = 0, w = 0;
  while (h < H - 1 || w < W - 1) {
    if ((h == H - 1 || table.at(h + 1).at(w) == '.' )&& (w == W - 1 ||
        table.at(h).at(w + 1) == '.')) {
      cout << "Impossible" << endl;
      return 0;
    } else if (h < H - 1 && table.at(h + 1).at(w) == '#') {
      h++;
      continue;
    } else if (w < W - 1 && table.at(h).at(w + 1) == '#') {
      w++;
      continue;
    }
    cout << "error" << endl;
    return 1;
  }

  cout << "Possible" << endl;
  return 0;
}

Measured memory_bytes: 3592
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define RFOR(i,a,b) for(int i = (int)(b-1);i>=(int)(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;
  
signed main(){
  ios::sync_with_stdio(false);
  cout.tie(0);
  cout.precision(20);
  
  string s;
  cin >> s;
  int l = 0,r = s.length() - 1;

  int ans = 0;
  while(l < r){
    if(s[l] != s[r]){
      ans++;
    }
    l++; r--;
  }

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

Measured memory_bytes: 256
$_=((("ab"x50).$/.("b"x100).$/)x10).(("c"x100).$/.("cd"x50).$/)x10;<>=~$";for$t(2..$'){s/a/#/}for$t(2..$`){s/d/./};s/a|b/./g;s/c|d/#/g;print"40 100\n$_"

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define MAX 1e18

using namespace std;

//FILE *fi=freopen("1.txt","r",stdin);

typedef pair<int,int> pii;

int n,m,q,l;
long long a[301][301],f[301][301];

void process()
{
    for (int k=1;k<=n;++k)
    {
        for (int u=1;u<=n;++u)
        {
            for (int v=1;v<=n;++v)
            {
                if (a[u][v]>a[u][k]+a[k][v])
                {
                    a[u][v]=a[u][k]+a[k][v];
                }
            }
        }
    }
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=n;++j)
        {
            if (a[i][j]<=l)
                f[i][j]=1;
        }
    }
    for (int k=1;k<=n;++k)
    {
        for (int u=1;u<=n;++u)
        {
            for (int v=1;v<=n;++v)
            {
                if (f[u][v]>f[u][k]+f[k][v])
                {
                    f[u][v]=f[u][k]+f[k][v];
                }
            }
        }
    }
}

void nhap()
{
    scanf("%d %d %d",&n,&m,&l);
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=n;++j)
        {
            if (i!=j)
                a[i][j]=MAX;
            f[i][j]=INT_MAX;
        }
    }
    for (int i=1;i<=m;++i)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        if (w<=l)
        {
            a[u][v]=a[v][u]=w;
        }
    }
    process();
    scanf("%d",&q);
    while (q--)
    {
        int s,t;
        scanf("%d %d",&s,&t);
        if (f[s][t]==INT_MAX)
            cout<<-1<<"\n";
        else cout<<f[s][t]-1<<"\n";
    }
}

int main()
{
    nhap();
    return 0;
}


Measured memory_bytes: 1920
n,m = map(int,input().split())
mod = 998244353

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

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = n+2*m + 100
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,max):
      fac[i] = fac[i-1]* i% mod
      inv[i] = mod - inv[mod%i] * (mod // i) % mod
      finv[i] = finv[i-1] * inv[i] % mod

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod


a = 0
for x in range(min(m,n)+1):
    if(3*m-x)%2==1:
        continue
    y = (3*m-x)//2
    a += com(n,x)*fac[y+n-1]*finv[y]*finv[n-1]
    a %= mod

b = fac[n-1+m-1] * finv[n-1] * finv[m-1] * n
b %= mod

ans = a-b
ans %= mod

print(ans)

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

using ll=long long;
const ll MOD=1e9+7;

ll powm(ll x,ll k){
    ll res=1;
    while(k){
        if(k&1) res=(res*x)%MOD;
        x=(x*x)%MOD;
        k>>=1;
    }
    return res;
}
ll inv(ll x){
    return powm(x,MOD-2);
}
ll comb(ll n,ll k){
    ll res=1;
    for(int i=0;i<k;i++){
        res*=(n-i)%MOD;
        res%=MOD;
    }
    for(int i=0;i<k;i++){
        res*=inv(i+1);
        res%=MOD;
    }
    return res;
}
int main(){
    ll n,d,x;
    while(cin>>n>>d>>x,n){
        vector<vector<ll>> dp(n+1,vector<ll>(n+1,0));
        dp[0][0]=1;
        for(int i=0;i<n;i++){
            vector<ll> sum(n+2,0);
            partial_sum(dp[i].begin(),dp[i].end(),sum.begin()+1,[](int x,int y){return (x+y)%MOD;});
            for(int j=0;j<=n;j++){
                dp[i+1][j]=(sum[j+1]+MOD-sum[max(j-x+2,0LL)])%MOD;
            }
        }
        ll res=0;
        for(int i=1;i<=min(n,d);i++){
            res+=(comb(d,i)*dp[i][n-i])%MOD;
            res%=MOD;
        }
        cout<<(res+MOD)%MOD<<endl;
    }

    return 0;   
}


Measured memory_bytes: 34276
#include <bits/stdc++.h>
#define REV(v) reverse(v.begin(), v.end());
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, start, stop) for (int i = start; i < stop; i++)
#define FORR(i, start, stop) for (int i = start; i > stop; i--)
#define SORT(v, n) sort(v, v + n);
#define SORTR(v, n) sort(v, v + n,greater<int>());
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.begin(), v.end(),greater<int>());
#define REMOVE(v,n) remove(vector<int> v,v+v.size(),int n)
#define ll long long
#define ull unsigned long long
#define pb(a) push_back(a)
#define INF 999999999
#define V(v,i,j) vector(v.begin() + i, v.begin() + j)
#define INSERT(va,vb) va.insert(va.end(), vb.begin(), vb.end())
using namespace std;
typedef vector<int> vint;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
const int MOD = 1000000007;
void chmin(int &a, int b) { if (a > b) a = b; }

//vector< vector<int> > v (size1, vector<int>(size2) );

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

    ll n;
    cin>>n;
    vector<ll> a(n);
    ll m=0;

    FOR(i,0,n){
        cin>>a[i];
        m=max(m,a[i]);
    }

    ll m2=0;
    ll a2;
    ll ans=0;
    FOR(i,0,n){
        a2=min(a[i],m-a[i]);
        if(a2>m2){
            m2=a2;
            ans=a[i];
        }
    }

    cout<<m<<' '<<ans<<endl;
    
    /*FOR(i,0,n){
        cout<<a[i]<<endl;
    }*/


}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REP(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

#define MAX_N 200005
class UnionFind
{
public:
  int par[MAX_N];
  int depth[MAX_N];
  int nGroup[MAX_N];

  UnionFind(int n) {
    init(n);
  }

  void init(int n) {
    for(int i=0; i<n; i++) {
      par[i] = i;
      depth[i] = 0;
      nGroup[i] = 1;
    }
  }

  int root(int x) {
    if(par[x] == x) {
      return x;
    } else {
      return par[x] = root(par[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;

    if(depth[x] < depth[y]) {
      par[x] = y;
      nGroup[y] += nGroup[x];
      nGroup[x] = 0;
    } else {
      par[y] = x;
      nGroup[x] += nGroup[y];
      nGroup[y] = 0;
      if(depth[x] == depth[y])
        depth[x]++;
    }
  }
};

int main() {
  int N, K, L;
  cin >> N >> K >> L;
  vector<int> P(K), Q(K), R(L), S(L);
  UnionFind U(N), V(N);
  rep(i, K) {
    cin >> P[i] >> Q[i];
    P[i]--, Q[i]--;
    U.unite(P[i], Q[i]);
  }
  rep(i, L) {
    cin >> R[i] >> S[i];
    R[i]--, S[i]--;
    V.unite(R[i], S[i]);
  }
  map<pair<int, int>, int> G;
  rep(i, N) {
    auto p = make_pair(U.root(i), V.root(i));
    if(G.count(p)) G[p]++;
    else G[p] = 1;
  }
  rep(i, N)
    cout << G[make_pair(U.root(i), V.root(i))] << ' ';
  cout << endl;
  return 0;
}



Measured memory_bytes: 18176
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstring>
#include <forward_list>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

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

const ll MOD = 1E+09 + 7;
const ll INF = 1E18;
const int MAX_N = 1E+05;

int N;

ll A[3 * MAX_N];
ll fds[MAX_N + 1], lds[MAX_N + 1];

ll solve();

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

    cin >> N;

    for (int i = 0; i < 3 * N; i++) {
        cin >> A[i];
    }

    cout << solve() << "\n";

    return 0;
}

ll solve()
{
    priority_queue<ll, vector<ll>, greater<ll>> fque;
    priority_queue<ll> lque;
    ll fbs = 0;
    ll lbs = 0;
    for (int i = 0; i < N; i++) {
        fque.push(A[i]);
        fbs += A[i];
    }
    for (int i = 2 * N; i < 3 * N; i++) {
        lque.push(A[i]);
        lbs += A[i];
    }

    ll ffds = 0;
    fds[0] = 0;
    for (int i = N; i < 2 * N; i++) {
        ll fmin = fque.top();
        if (fmin < A[i]) {
            fque.pop();
            fque.push(A[i]);
            fds[i - N + 1] = ffds + A[i] - fmin;
        } else {
            fds[i - N + 1] = ffds;
        }
        ffds = fds[i - N + 1];
    }

    ll llds = 0;
    lds[N] = 0;
    for (int i = 2 * N - 1; i >= N; i--) {
        ll lmax = lque.top();
        if (lmax > A[i]) {
            lque.pop();
            lque.push(A[i]);
            lds[i - N] = llds - A[i] + lmax;
        } else {
            lds[i - N] = llds;
        }
        llds = lds[i - N];
    }

    ll dans = -INF;
    for (int i = 0; i <= N; i++) {
        dans = max(dans, lds[i] + fds[i]);
    }

    return fbs - lbs + dans;
}

Measured memory_bytes: 8692
#include <bits/stdc++.h>
//Remove below header file if c++ version greater than 14
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>

#define ll long long int
#define pb push_back
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl '\n'
#define deb(x) cout << #x << " "<< x << endl;
#define fo(i, n) for(i=0; i<n; i++)
#define Fo(i, k, n) for(i=k; i<n; i++)

using namespace std;
using mii=map<int, int>;
using mll=map<ll, ll>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int mod = 1000000007;

ll desc(ll x, ll y)
{
    return x > y;
}

int main() {
    fastIO
    int n, i;
    cin >> n;
    vi arr(n, 0);
    fo(i, n)
    {
        cin >> arr[i];
    }
    int c = 0;
    for(i = 1;i < n - 1;i++)
    {
        if(arr[i] > arr[i - 1] && arr[i] < arr[i + 1])
            c++;
        else if(arr[i] < arr[i - 1] && arr[i] > arr[i + 1])
            c++;
    }
    cout << c << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<deque>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<complex>
#include<chrono>
#include<random>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

ll gcd(ll n, ll m) {
	ll tmp;
	while (m!=0) {
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m) {
	return abs(n * m) / gcd(n, m);//gl=xy
}
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
using namespace std;

using P=pair<ll,ll>;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<P>a(n+m+5);
    rep(i,n){
        cin>>a[i].first;
        a[i].second=1;
    }
    rep(i,m){
        cin>>a[i+n].second>>a[i+n].first;
    }
    sort(all(a));
    reverse(all(a));
    ll sum=0;
    int fin=n+m;
    rep(i,fin){
        if(a[i].second<n){
            sum+=a[i].first*a[i].second;
            n-=a[i].second;
        }
        else {
            sum+=a[i].first*n;
            break;
        }
    }
    cout<<sum;
}

int main(){
	ios::sync_with_stdio(false);
  cin.tie(0);
	cout<<fixed<<setprecision(15);
  solve();
	return 0;
}


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

long long dp[110][100010];

int main()
{
    int n, k;
    cin >> n >> k;
    int w[n], v[n];
    for(int i=1; i<=n; i++){
		cin >> w[i] >> v[i];
    }

    for(int i=1; i<=n; i++){
		for(int j=1; j<=k; j++){
			dp[i][j] = dp[i-1][j];
			if(j-w[i]>=0){
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
			}
		}
    }

    cout << dp[n][k];

    return 0;
}


Measured memory_bytes: 81704
n = gets.to_i
x = gets.split.map(&:to_i)
pmax = x.max

dist = Hash.new(0)
1.upto(pmax) do |p|
  sum = x.inject(0) do |r, a|
    r + ((a - p)**2)
  end
  dist[p] = sum
end

puts dist.values.min

Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;

int main() {
    string s;
    int k;
    cin >> s >> k;
    rep(i,s.size()) {
        char& c = s[i];
        if(c == 'a') continue;
        int nexta = 'z'-c+1;
        if(nexta <= k) {
            k -= nexta;
            c = 'a';
        }
    }
    if(k > 0) {
        k %= 26;
        s[s.size()-1] += k;
        if(s[s.size()-1] > 'z') s[s.size()-1] -= 26;
    }
    cout << s << endl;
}

Measured memory_bytes: 512
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

int i,n,m,block=0,ans=0;
int c[500010],b[500010],pos[500010];
int h[1000010]={0};
struct zht{
	int l,r,id;
}a[500010];

bool cmp(zht a,zht b){if (pos[a.l]==pos[b.l]) return a.r<b.r;
	return a.l<b.l;
}

inline int read(){
	char x;	int p=0;
	x=getchar();
	while (x<48||x>57) x=getchar();
	while (x>=48&&x<=57)	p=p*10+x-48,x=getchar();
	return p;
}

inline void update(int x,int add){
	if (add==1)	{
		if (!h[c[x]])	ans++;
		h[c[x]]++;	}
	if (add==0)	{
		if (h[c[x]]==1)	ans--;
		h[c[x]]--;	}
	return;
}

inline void Solve(){
	int i=0,l=1,r=0;
		for(i=1;i<=m;i++){
		for(;r<a[i].r;r++)	update(r+1,1);
		for(;r>a[i].r;r--)	update(r,0);
		for(;l<a[i].l;l++)	update(l,0);
		for(;l>a[i].l;l--)	update(l-1,1);
		if(a[i].l==a[i].r){
			b[a[i].id]=1;
			continue;
		}
		b[a[i].id]=ans;
	}
	return;
}

int main(){
	#ifdef __Marvolo
	freopen("zht.in","r",stdin);
	freopen("zht.out","w",stdout);
	#endif
	scanf("%d",&n);	scanf("%d",&m);
	for (i=1;i<=n;i++)	c[i]=read();
	for (i=1;i<=m;i++){
		a[i].l=read();	a[i].r=read();	a[i].id=i;
	}
	block=int(sqrt(n));
	for(i=1;i<=n;i++)	pos[i]=(i-1)/block+1;
	sort(a+1,a+1+m,cmp);
	Solve();
	for (i=1;i<=m;i++)	printf("%d\n",b[i]);
	return 0;
}

Measured memory_bytes: 17268
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
int N, M, a, b, c[2]; bool vis[100009]; vector<int> g[100009];
void dfs(int pos) {
	vis[pos] = true;
	for (int i : g[pos]) {
		if (!vis[i]) dfs(i);
	}
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b; a--, b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for (int i = 0; i < 2; i++) {
		fill(vis, vis + N, false);
		dfs(i);
		for (int j = 0; j < N; j++) c[i] += vis[j];
	}
	int v = min(c[0], c[1]);
	cout << 1LL * v * (v - 1) / 2 + 1LL * (N - v) * (N - v - 1) / 2 - M << endl;
	return 0;
}

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

int main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	long long a, b; cin >> a >> b;
	long long c = min(a, b / 2);
	a -= c;
	b -= c * 2;
	cout << c + b / 4 << endl;
}

Measured memory_bytes: 3600
#include <iostream>
#include <string>
#include <vector>

#define rep(i,n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  if (A + B >= C) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
#include <numeric>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265359;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };



signed main() {
	int n, k;
	string s;

	cin >> n >> k;
	cin >> s;

	s[k-1] = tolower(s[k-1]);

	cout << s << endl;






	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    
  int h,w;
  int i,j;
  scanf("%d",&h);
  scanf("%d",&w);
  while(!((h==0) && (w==0))){
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
        if ((i%2==0) && (j%2==0)){
          printf("#");
        }else if ((i%2==0) && (j%2==1)){
          printf(".");
        }else if ((i%2==1) && (j%2==0)){
          printf(".");
        }else if ((i%2==1) && (j%2==1)){
          printf("#");
        }
      }
      printf("\n");
    }
    printf("\n");
    scanf("%d",&h);
    scanf("%d",&w);
  }


  return 0;
}



Measured memory_bytes: 2104