akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int main(){
  int ans=0;
  string a1,a2;
  cin>>a1>>a2;
  for(int i=0;i<a1.size();i++){
    if(a1[i]!=a2[i]) ans++;
  }
  cout<<ans;
  return 0;
}


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

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

a.sort()

can = True

if a[0] == 0:
    for i in range(1,n):
        if i % 2 != 1:
            if a[i] != i:
                can = False
                break
        else:
            if a[i] != i + 1:
                can = False
                break
    if can:
        print((2 ** int((n-1)/2))% (10 ** 9 + 7))
    else:
        print(0)
elif a[0] == 1:
    for i in range(0,n):
        if i % 2 != 1:
            if a[i] != i + 1:
                can = False
                break
        else:
            if a[i] != i:
                can = False
                break
    if can:
        print((2 ** int(n/2))% (10 ** 9 + 7))
    else:
        print(0)
else:
    print(0)


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

double a[3001];
double dp[3001][3001];
int main(){
  int n;
  cin >> n;
  for(int i=1;i<=n;i++){
    cin >> a[i];
  }
  memset(dp,0,sizeof(dp));
  dp[0][0]=1;
  for(int i=1;i<=n;i++){
    for(int j=0;j<=(i+1);j++){
      if(j==0){
        dp[i][j] = dp[i-1][j]*(1-a[i]);
      }
      else{
        dp[i][j] = dp[i-1][j]*(1-a[i]) + dp[i-1][j-1]*a[i];
      }
    }
  }
  double ans=0.0;
  for(int i=(n+1)/2;i<=n;i++) {
    ans+=dp[n][i];
  }
  printf("%.10f\n",ans );
}


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

int main() {
  string S, T, U;
  int A, B;
  cin >> S >> T >> A >> B >> U;
  
  if (S == U) {
    A--;
  }
  else {
    B--;
  }
  
  cout << A << " " << B << endl;
  
  return 0;
}


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

using namespace std;

const double EPS = 1e-10;
const double d_INF = 100000000.0;
const int I_INF = 1000000000;

int n;
string name[100];
int weight[100];
int cap[100];
vector<int> t_path;
vector<int> path;
double height;

void dfs(int s, int c, int sum, double g){
  if(s == (1<<n)-1){
    if(height > g){
      path = t_path;
      height = g;
    }
    return;
  }
  if(height < g) return;
  int pos = 1;
  int div = 0;
  for(int i=0;i<n;i++){
    if((1<<i) & s){
      ++pos;
      div += weight[i];
    }
  }
  for(int i=0;i<n;i++){
    if((1<<i) & s) continue;
    if(weight[i] > c) continue;
    t_path.push_back(i);
    dfs(s|(1<<i), min(c-weight[i], cap[i]), sum+pos*weight[i], (double)(sum+pos*weight[i])/(div+weight[i]));
    t_path.pop_back();
  }
}

void solve(){
  height = d_INF;
  dfs(0, I_INF, 0, 0.0);
  for(int i=0;i<path.size();i++){
    cout << name[path[i]] << endl;
  }
}

main(){
  while(cin >> n && n){
    for(int i=0;i<n;i++){
      cin >> name[i] >> weight[i] >> cap[i];
    }
    solve();
  }
  return 0;
}

Measured memory_bytes: 912
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { a = b; return true;}
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) { a = b; return true;}
    return false;
}
int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k;cin>>n>>k;
    int cnt = (n-1)*(n-2)/2;
    if(cnt<k){
        cout << -1 << endl;
        return 0;
    }
    vector<vector<bool> > chk(n,vector<bool>(n,false));
    rep(i,n){chk[i][i]=true;}
    vector<pair<int,int>> res;
    repr(i,1,n){
        res.emplace_back(0,i);
        chk[0][i]=chk[i][0]=true;
    }
    int source=1,target=2;
    while(cnt>k){
        if(!chk[source][target]){
            res.emplace_back(source, target);
            chk[source][target] = chk[target][source] = true;
            cnt--;
        }
        if(target==n-1){
            source++;
            target=0;
        }
        else{
            target++;
        }
    }
    cout << res.size() << endl;
    for(auto x:res){
        cout << x.first+1 << " " << x.second+1 << endl;
    }
    return 0;
}


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

typedef long long LL;
const int N = 1e6+7, M = 998244353;

int fr[N];
LL msum[N], msqsum[N];
LL gcdsum[N];

LL power(LL a, LL p) {
    if (p==0)   return 1;
    LL ans = power(a, p/2);
    ans = (ans * ans)%M;
    if (p%2)    ans = (ans * a)%M;
    return ans;
}


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

    int n;
    cin>>n;

    for (int i=1; i<=n; i++) {
        int x;
        cin>>x;
        fr[x]++;
    }

    for (int i=1; i<N; i++) {
        for (int j=i; j<N; j+=i) {
            msum[i] += 1LL*j*fr[j];
            msqsum[i] += 1LL*j*j*fr[j];
        }
    }

    for (int i=1; i<N; i++) {
        msum[i] %= M;
        msqsum[i] %= M;
        gcdsum[i] = (msum[i]*msum[i]+M-msqsum[i])%M;
        if (gcdsum[i]%2)    gcdsum[i] += M;
        gcdsum[i]/=2;
    }

    long long ans = 0;
    for (int i=N-1; i>0; i--) {
        for (int j=2*i; j<N; j+=i)
            gcdsum[i] = (gcdsum[i] + M - gcdsum[j])%M;

        ans = (ans + gcdsum[i] * power(i, M-2))%M;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 27648
#include <bits/stdc++.h>
using namespace std;
#define rep(i,c) for(int i=0;i<c;++i)
int  main(){
 int a;
 cin >> a;
 vector<int>d(a);
 vector<int> b(a);
 vector<int>c(a-1);
 int count = 0;
 for(int i=0;i<a;i++){
    cin >> d[i];
    d[i] = d[i]-1;
 }
 for(int i=0;i<a;i++){
    cin >>b[i];
 }
 for(int i=0;i<a-1;i++){
    cin >> c[i];
 }
for(int i=0;i<a;i++){
   count +=b[d[i]];
   if(d[i+1]==d[i]+1){
      count +=c[d[i]];
   }
}
 cout << count << endl;
return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int arr[100010][5];
int dp[100010][5];

int vac(int a, int b){
	if(a == 0) return 0;
	if(dp[a][b] != -1) return dp[a][b];
	
	for(int i = 1; i <= 3; i++){
		if(i != b){
			dp[a][b] = max(dp[a][b], vac(a - 1,i) + arr[a][i]);
		}
	}
	
	return dp[a][b];
}

int main (){
	memset(dp,-1,sizeof dp);
	int n;
	cin >> n;
	for(int i = 1; i <=n; i++){
		cin >> arr[i][1] >> arr[i][2] >> arr[i][3];
	}
	
	
	int ans = 0;
	for(int i = 1; i <= 3; i++){
		ans = max(ans , vac(n - 1, i) + arr[n][i]);
	}
	
	cout << ans << endl;
	
}

Measured memory_bytes: 11904
//in the name of god
#include <bits/stdc++.h>
using namespace std;
#define MAX_N (int)1e5+20
#define INF 1e18+20
#define pb push_back
#define F first
#define S second
typedef long long LL;
#define int LL
typedef pair<int,int> pii;
typedef pair<int,pii> pI;
const int delta=(int)1e9+7;
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
int n,g,x,ans;
main(){
	ios_base::sync_with_stdio(0);
	cin>>n;
	while(n--){
		cin>>x; g=gcd(g,x);
	}
	while(g%2==0){
		++ans; g/=2;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.math.BigInteger;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] str = in.readLine().split(" ");
    int a = Integer.parseInt(str[0]);
    int b = Integer.parseInt(str[1]);
    in.close();
    
    BigInteger ba = BigInteger.valueOf(a);
    BigInteger bb = BigInteger.valueOf(b);
    BigInteger gcd = ba.gcd(bb);
    System.out.println(ba.multiply(bb).divide(gcd).toString());
  }
}
    

Measured memory_bytes: 22612
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>
#include <cmath>
#include <functional>
#include <map>
#include <cstdlib>
#include <stack>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;
using Graph = Vvec<int>;

template <class T>
void debug(T& v)
{
    for(auto& x: v) cout << x << " ";
    cout << endl;
}

int main()
{
    string S;
    cin >> S;
    for(int i=0; i<3; i++) cout << S[i];
    cout << endl;
}

Measured memory_bytes: 3596
#include<stdio.h>
#include<stdbool.h> //ブーリアン型(Boolean datatype)で、真理値の２つの値をとる
#define SWAP(type,a,b) {type temp = a; a = b; b = temp;}  //SWAPとは、2つの変数の値を交換するマクロや関数

static const int N = 100;

int bubbleSort(int A[], int n){
  int count = 0;
  int i, j;
  bool flag = 1;
  for(i = 0; flag ; i++){
    flag = 0;
    for(j = n -1; j >= i + 1; j--){
      if(A[j] < A[j-1]){
        SWAP(int,A[j], A[j-1] );
        flag = 1;
        count++;
      }
    }
  }
  return count;
}

int main(){
  int A[N+1], n, i, count;
  scanf("%d",&n);
  for(i = 0; i < n; i++) scanf("%d", &A[i]);
  count = bubbleSort(A, n);
  for(i = 0; i < n ; i++){
    if(i) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
  printf("%d", count);
  printf("\n");
  return 0;
}



Measured memory_bytes: 2128
n = int(input())
A = list(map(int, input().split()))

calc = []
for i in range(n):
    calc.append(A[i] - (i + 1))

calc.sort()

b = calc[n // 2]

ans = 0
for i in range(n):
    ans += abs(A[i] - (b + i + 1))

print(ans)

Measured memory_bytes: 26020
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] line = Stream.of(sc.nextLine().split(" ", 0)).mapToInt(Integer::parseInt).toArray();
		int[] A = Stream.of(sc.nextLine().split(" ", 0)).mapToInt(Integer::parseInt).toArray();
		int ind =0;
		int lowerans = 0;
		int upperans = 0;
		int con =1;

		//X ～ 0
		while (con < line[2] && ind < line[1]) {
			if (A[ind] == con) {
				lowerans++;
				ind++;
			}
			con++;
		}

		//X ～ N
		con = line[2] + 1;
		while (con < line[0] && ind < line[1]) {
			if (A[ind] == con) {
				upperans++;
				ind++;
			}
			con++;
		}

		if (lowerans <= upperans) {
			System.out.println(lowerans);
		}else {
			System.out.println(upperans);
		}

	}
}


Measured memory_bytes: 36028
MOD = 10**9 + 7

N = int(input())
S = input().rstrip()

is_left = [(i%2 == 0) ^ (x == "W") for i, x in enumerate(S)]

answer = 1
left = 0
for bl in is_left:
    if bl:
        left += 1
    else:
        answer *= left
        left -= 1
        answer %= MOD

if left != 0:
    answer = 0
    
for i in range(1, N+1):
    answer *= i
    answer %= MOD

print(answer)

Measured memory_bytes: 5096
#include <stdio.h>

int main(void){
  
  int H,A;
  scanf("%d",&H);
  scanf("%d",&A);
  int ans;
  
  if(H%A == 0)  ans = H/A;
  if(H%A != 0)  ans = H/A + 1;
  
  printf("%d\n",ans);
  
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define REP(i, m, n) for(ll i = (ll)m; i < (ll)n; i++)
#define PER(i, m, n) for(ll i = (ll)m; i > (ll)n; i--)
#define INF 1e9
#define ALL(v) v.begin(), v.end()
#define _GLIBCXX_DEBUG

template <uint MD> struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(uint(ull(v) * r.v % MD)); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<1000000007>;

const double PI = 3.14159265358979323846;

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}

int main(){
    ll n;
    cin >> n;
    vector<ll> v(n);
    REP(i, 0, n) cin >> v[i];
    Mint ans = 0;
    Mint sum = 0;

    PER(i, n-1, 0){
        sum += v[i];
        ans += sum*v[i-1];
    }

    cout << ans << endl;
}


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

typedef long long ll;
typedef pair<int,int> ii;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int n; cin>>n; cout << n*(n+1)/2 << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int a[60];
int main()
{
int n,t;
cin>>n;
bool check=true;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=1;i<n;i++)if(a[i]<a[i-1])check=false;
if(check){cout<<"YES"<<endl;return 0;}
else check=true;
for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)
{
t=a[i];a[i]=a[j];a[j]=t;
for(int i=1;i<n;i++)if(a[i]<a[i-1])check=false;
if(check){cout<<"YES"<<endl;return 0;}
else{t=a[i];a[i]=a[j];a[j]=t;check=true;}
}
cout<<"NO"<<endl;
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int K, A, B; cin >> K >> A >> B;
  for(int i=A;i<=B;i++){
    if(i%K==0){
      cout << "OK" << endl;
      return 0;
    }
  }
  cout << "NG" << endl;
  return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <fstream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <bitset>
#include <limits>
#include <algorithm>

int MOD_BIG = 1000000007;
int MOD_BIG2 = 998244353;
using std::string;
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using ll = long long;
using pint = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using std::vector;

#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)

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

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

int main() {
    
    int H1, M1, H2, M2, K;
    cin >> H1 >> M1 >> H2 >> M2 >> K;
    
    cout << std::max(0, (H2-H1)*60 + (M2-M1) - K) << endl;
    
    return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

int H,N,P,M,K;
int sw[505];
double dp[505][105][105];
double prob[505];

int main(){
  memset(sw,-1,sizeof(sw));
  cin>>H>>N>>P>>M>>K;
  P--;
  rep(i,M){
    int a,b;
    cin>>a>>b;
    b--;
    sw[a]=b;
  }
  dp[H][0][P]=1.0;
  rep(j,K){
    prob[j]=1.0/(double)((N-1)*(H-M-j));
  }
  for(int i=H;i>=1;i--)rep(j,K+1)rep(k,N){
    if(sw[i]==-1){
      if(j<K){ // put
        if(k>0){
          dp[i-1][j+1][k-1]+=dp[i][j][k]*prob[j]*(j+1);
        }
        if(k<N-1){
          dp[i-1][j+1][k+1]+=dp[i][j][k]*prob[j]*(j+1);
        }
        if(N>2){
          if(k==0||k==N-1) dp[i-1][j+1][k]+=dp[i][j][k]*prob[j]*(double)(N-2)*(j+1);
          else dp[i-1][j+1][k]+=dp[i][j][k]*prob[j]*(double)(N-3)*(j+1);
        }
      }
      {
        dp[i-1][j][k]+=dp[i][j][k];
      }
    }else{
      if(sw[i]==k){
        dp[i-1][j][k+1]+=dp[i][j][k];
      }else if(sw[i]==k-1){
        dp[i-1][j][k-1]+=dp[i][j][k];
      }else{
        dp[i-1][j][k]+=dp[i][j][k];    
      }
    }
  }
  double res=0;
  rep(k,N){
    maxch(res,dp[0][K][k]);
  }
  printf("%.10f\n", res);
  return 0;
}



Measured memory_bytes: 46256
while True:
    num = int(input())
    if num == 0:
        break
    
    L = []
    start = set()
    for _ in range(num):
        w, a, b = [int(x) for x in input().split()]
        L.append([w,a,b])
        start.add(a)
    
    f = 0
    for t in sorted(start):
        wt  = 0
        for l in L:
            if t >= l[1] and t < l[2]:
                wt += l[0]
        if wt > 150:
            f += 1
    
    if f > 0:
        print("NG")
    else:
        print("OK")
        
        


Measured memory_bytes: 5620
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    string s;
    cin >> s;
    REP(i,0,s.size()) {
        if (i % 2 == 0) {
            if (s[i] == 'L') {
                cout << "No" << endl;
                return;
            }
        } else {
            if (s[i] == 'R') {
                cout << "No" << endl;
                return;
            }
        }
    }
    cout << "Yes" << endl;
}

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

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

#define rep(i, n) for ( ll i = 0; i < (n); ++i )
#define reps(i, n) for ( ll i = 1; i <= (n); ++i )
#define _rep(i, n) for ( ll i = (n) - 1; i >= 0; --i )
#define _reps(i, n) for ( ll i = n; i > 0; --i )
#define all(x) (x).begin(), (x).end()
#define _all(x) (x).rbegin(), (x).rend()

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

int main( void )
{
	ll n, m, k;
	cin >> n >> m >> k;

	vector<ll> a(n + 1);
	reps ( i, n ) {
		cin >> a[i];
		a[i] += a[i - 1];
	}

	vector<ll> b(m + 1);
	reps ( i, m ) {
		cin >> b[i];
		b[i] += b[i - 1];
	}

	ll cnt = 0;
	ll j = m;
	for ( ll i = 0; i <= n; i++ ) {
		if ( a[i] > k ) {
			break;
		}

		while ( (a[i] + b[j]) > k ) {
			j--;
		}
		cnt = max(cnt, i + j);
	}

	cout << cnt << endl;

	return 0;
}


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

int main() {
    int N,s;
    cin >> N;
    vector<int> d(2*N);
    rep(i,2*N) {
        cin >> d.at(i);
    }
    s=0;
    for (int j =0; j< 2*N; j=j+2){
        if(d.at(j)==d.at(j+1)) {
            s=s+1;
        }
        else{
            s=0;
        }
        if(s==3){
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
}   

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

int main() {
  int n, s1, s2, tmp;
  s1 = 0;
  s2 = 0;
  std::cin >> n;
  
  std::vector<int> a(n);

  for (int i = 0; i < n; i++) {
    std::cin >> a.at(i);
  }
  
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - 1; j++) {
      if (a.at(j+1) > a.at(j)) {
        tmp = a.at(j);
        a.at(j) = a.at(j+1);
        a.at(j+1) = tmp;
      }
    }
  }
  
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0) {
      s1 += a.at(i);
    } else {
      s2 += a.at(i);
    }
  }
  
  std::cout << s1 - s2 << std::endl;
}

Measured memory_bytes: 256
/*Code by Codercjh*/
#include<bits/stdc++.h>
#define fr(i,a,b) for(int i=(a);i<=(b);++i)
#define rf(i,a,b) for(int i=(a);i>=(b);--i)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;
typedef long long ll;
template<typename T>
inline void read(T &x){
	char c=getchar();T fh=0;bool f=false;
	while(!isdigit(c))f|=(c=='-'),c=getchar();
	while(isdigit(c))fh=(fh<<1)+(fh<<3)+(c^48),c=getchar();
	x=f?-fh:fh;
	return;
}
char s[200005],t[200005];
int main(){
    cin>>s>>t;
	fr(i,0,strlen(s)-1)if(s[i]!=t[i])return puts("No"),0;
	puts("Yes"); 
	return 0;
}


Measured memory_bytes: 3624
import java.util.Arrays;
import java.util.Scanner;

//Overlaps of Seals
public class Main{

	static class P{
		public double x, y;
		public P(double x, double y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static class R implements Comparable<R>{
		public double minx, maxx, miny, maxy;
		public P[] p;
		public int prob;
		boolean[] mark;
		public R(boolean[] u, double minx, double maxx, double miny, double maxy) {
			this.minx = minx;
			this.maxx = maxx;
			this.miny = miny;
			this.maxy = maxy;
			p = new P[4];
			p[0] = new P(minx, miny);
			p[1] = new P(minx, maxy);
			p[2] = new P(maxx, miny);
			p[3] = new P(maxx, maxy);
			mark = new boolean[n];
			prob = 0;
			for(int i=0;i<n;i++){
//				if(u[i]){
					if(minx<=seal[i].x&&seal[i].x<=maxx && miny-1<=seal[i].y&&seal[i].y<=maxy+1){
						mark[i]=true;
						prob++;
					}
					else if(minx-1<=seal[i].x&&seal[i].x<=maxx+1 && miny<=seal[i].y&&seal[i].y<=maxy){
						mark[i]=true;
						prob++;
					}
					else {
						boolean f = false;
						for(int j=0;j<4;j++){
							if(Math.hypot(seal[i].x-p[j].x, seal[i].y-p[j].y)<=1){
								f = true;
								break;
							}
						}
						if(f){
							mark[i] = true;
							prob++;
						}
					}
//				}
			}

		}
		public void find(){
//			System.out.println("FIND MAX: " + max);
//			if(minx<=2.3 && 2.3<=maxx && miny<=4.6&&4.6<=maxy)
//				System.out.println("PROB FIND:" + prob + " MAX: " + max);
			if(prob<=max)return;
			if(maxx-minx<0.000001){
//				System.out.println("PROB:" + prob);
				max = Math.max(max, prob);
				return;
			}
			R[] r = new R[4];
			double midx = (minx+maxx)/2;
			double midy = (miny+maxy)/2;
			r[0] = new R(mark, minx, midx, miny, midy);
			r[1] = new R(mark, midx, maxx, miny, midy);
			r[2] = new R(mark, minx, midx, midy, maxy);
			r[3] = new R(mark, midx, maxx, midy, maxy);
			Arrays.sort(r);
			for(int i=0;i<4;i++)r[i].find();
		}
		public int compareTo(R o) {
			return o.prob-prob;
		}
	}
	
	static int n;
	static int max;
	static P[] seal;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			n = sc.nextInt();
			if(n==0)break;
			seal = new P[n];
			for(int i=0;i<n;i++){
				String[] s = sc.next().split(",");
				seal[i] = new P(Double.parseDouble(s[0]), Double.parseDouble(s[1]));
			}
			boolean[] u = new boolean[n];
			Arrays.fill(u, true);
			max = 0;
			R r = new R(u, 0, 10, 0, 10);
			r.find();
			System.out.println(max);
		}
	}
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[200005][61];
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;++i)
	 cin>>a[i][0];
	for(int i=1;i<=60;++i)
	 for(int j=1;j<=n;++j)
	  a[j][i]=a[a[j][i-1]][i-1];
	long long i=1;
	for(long long j=60;j>=0;--j)
	 if((1ll<<j)<=k) i=a[i][j],k-=(1ll<<j);
	cout<<i;
	return 0;
}

Measured memory_bytes: 98944
//***in the name of GOD***
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define str string

int main(){
  str s;
  cin >> s;
  for(int i = 0; i < s.size(); i++){
    if((i % 2) && (s[i] == 'R')){
      cout << "No";
      return 0;
    }
    if((i % 2 == 0) && (s[i] == 'L')){
        cout << "No";
        return 0;
    }
  }
  cout << "Yes";
}


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

using namespace std;
using   ll=long long;

#define fast            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define endl            "\n"
#define pb              push_back
#define mp              make_pair
#define F               first
#define S               second
#define int             long long int
#define pll                pair<int , int>

#define ALL(v)          v.begin(),v.end()
#define ALLR(v)         v.rbegin(),v.rend()
#define pii             3.14159265358979323
#define inf             LLONG_MAX
#define ones(x)         __builtin_popcount(x)
#define fill(a,b)       memset(a,b,sizeof(a))
#define mod             1000000007
#define hell            998244353 

ll mod_pow(ll a,ll b,ll m) 
{
    ll res = 1;
    while(b)    
    {
        if(b&1)     
        {
            res=(res*a) % m;
        }
        a=(a*a) % m;
        b>>=1;
    }
    return res;
}

ll mod_inverse(ll a) 
{
    return mod_pow(a , mod-2 , mod);
}

void solve() 
{
	int n , k;
	
	cin >> n >> k;
	
	int a[n];
	
	int mx = 0;
	
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
		mx = max(mx , a[i]);
	}
	
	int l = 1;
	int r = mx;
	int ans = mx;
	
	while(l <= r) {
		int mid = (l+r)/2;
		
		int tot = 0;
		
		for(int i = 0; i < n; ++i) {
			tot += ((a[i]-1)/mid);
		}
		
		if(tot <= k) {
			ans = mid;
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	
	cout << ans;
}

signed main() {
    fast;
    
    int t = 1;
    
    //cin >> t;
    
    while(t--) {
        solve();
    }
 
    return 0;
}


Measured memory_bytes: 5152
n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
B = [list(map(int,input().split())) for i in range(m)]
C = [[0]*l for i in range(n)]

for i in range(n):
    for j in range(l):
        for k in range(m):
            C[i][j] += A[i][k]*B[k][j]

for row in range(n):
    print(str(C[row][0]), end = "")
    for i in range(1,l):
        print(f" {C[row][i]}", end = "")
    print()


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

#define INF 100100100
#define MOD 1000000007

using namespace std;

int main(int argc, char const* argv[])
{
   int N,M,X,Y;
   cin >> N >> M >> X >> Y ;
   vector<int>x(N),y(M);
   for(int i=0;i<N;i++) cin >> x[i];
   for(int i=0;i<M;i++) cin >> y[i];
   sort(x.begin(),x.end());
   sort(y.begin(),y.end());
   bool war = true;
   for(int i=X+1;i<=Y;i++){
      if(x[N-1] < i && y[0] >= i){
         war = false;
         break;
      }
      else continue;
   }
   if(war)cout << "War";
   else cout << "No War";
   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define base 31
#define MOD 1e9+7
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORs(i, a, b) for(int i = a; i >= b; i--)
#define REP(i, a, b) for(int i = a; i < b; i++)
#define __FOR(i, a, b, k) for(int i = a; i <= b; i+= k)
#define __REP(i, a, b, k) for(int i = a; i < b; i+= k)
#define pb push_back
#define _io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define Read_ freopen("input.inp", "r", stdin)
#define Write_ freopen("output.out", "w", stdout);
using namespace std;
typedef pair <int, int> ii;
typedef vector <ii> vii;
#define fi first
#define se second
#define mp make_pair
#define N  52
int main(){
    _io; 
    string s;
    cin>>s;
    if (s[s.size()-1]=='s'){
        s=s+"es";
        cout<<s;
    }
    else cout<<s+"s";
}




Measured memory_bytes: 3664
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

city = [e, d, c, b, a]
result = 'Yay!'
for i, c in enumerate(city):
    for u in city[i + 1:len(city)]:
        if (c - u) > k:
            result = ':('
            break;
print(result)

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

bool isprime(int x){
  if(x == 2){
    return true;
  }
  if(x < 2 || x%2==0){
    return false;
  }
  int i = 3;
  while( i <= sqrt(x)){
    if(x%i==0){
      return false;
    }
    i = i + 2;
  }

 return true;
}

int main(){
    int n, x, count=0;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> x;
        if(isprime(x)) count++;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 3068
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll inf=1000000000000000000;
long double pi=3.14159265358979323846L;
double eps=1e-12;
#define rep(i,m,n) for(int i=m;i<n;i++)
#define rrep(i,n,m) for(int i=n;i>=m;i--)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll gya[1000010];
ll kai[1000010];
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll x,y;cin>>x>>y;
    if(abs(x-y)<=1)cout<<"Brown"<<endl;
    else cout<<"Alice"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename Q_temp>
using smaller_queue = priority_queue<Q_temp, vector<Q_temp>, greater<Q_temp>>;

const ll MOD = (ll)(1e9 + 7);
const int INF = (int)1e9;
const ll LINF = (ll)4e18;
const double PI = acos(-1.0);

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define possible(n) cout << ((n) ? "possible" : "impossible") << endl
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << endl;

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

  int n, m;
  cin >> n >> m;
  bool ac[100010] = {};
  int pe[100010] = {};
  rep(i, m)
  {
    int p;
    string s;
    cin >> p >> s;
    p--;
    if (s == "AC")
    {
      ac[p] = true;
    }
    else
    {
      if (!ac[p])
      {
        pe[p]++;
      }
    }
  }
  int sum_ac = 0, sum_pe = 0;
  rep(i, n)
  {
    sum_ac += ac[i];
    if (ac[i])
      sum_pe += pe[i];
  }
  cout << sum_ac << " " << sum_pe << endl;
  return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_map>

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

using namespace std;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

struct Point {
    int x;
    int y;
    int d;
    Point(){}
    Point(int x, int y, int d) {
        this-> x = x;
        this-> y = y;
        this-> d = d;
    }
};

int main(){
    int h,w; cin >> h >> w;
    int white = 0;
    vector<int> table[h];
    vector<int> visited[h];
    rep(i, h) {
        rep(j, w) {
            char c; cin >> c;
            if(c == '.') {
                table[i].push_back(0);
                white++;
            }
            else{
                table[i].push_back(1);
            }
            visited[i].push_back(0);
        }
    }
    queue<Point> q;
    q.push(Point(0,0,1));
    int shortest = -1;
    while(!q.empty()) {
        Point p = q.front();
        q.pop();
        if(p.x < 0 || p.x >= h || p.y < 0 || p.y >= w)
            continue;
        if(table[p.x][p.y])
            continue;
        if(visited[p.x][p.y])
            continue;
        visited[p.x][p.y] = 1;
        if(p.x == h-1 && p.y == w-1) {
            shortest = p.d;
            break;
        }
        q.push(Point(p.x-1, p.y, p.d+1));
        q.push(Point(p.x+1, p.y, p.d+1));
        q.push(Point(p.x, p.y-1, p.d+1));
        q.push(Point(p.x, p.y+1, p.d+1));
    }
    if(shortest == -1) {
        cout << -1 << endl;
        return 0;
    }
    cout << white - shortest << endl;
}


Measured memory_bytes: 256
def pow2(x):
    if x == 0:
        return 1
    elif x % 2 == 0:
        return (pow2(x/2) ** 2) % (10**9 + 7)
    else:
        return 2 * pow2(x-1)

N = int(input())
a_arr = list(map(int, input().split()))
flag = 0

count_arr = []
for _ in range((N+1)//2):
    count_arr.append(0)

if N%2 == 0: # a = N-1, N-3, ... , 1, 3, ...
    for a in a_arr:
        if a%2 == 0:
            flag = 1
            break
        else:
            count_arr[(a-1)//2] += 1
            if count_arr[(a-1)//2] > 2:
                break
else:
    for a in a_arr: # N-1, N-3, ... 0, 2, ..., N-1
        if a%2 == 1:
            flag = 1
            break
        elif a == 0:
            if count_arr[0] > 0:
                flag = 1
                break
            else:
                count_arr[0] += 1
        else:
            if count_arr[a//2] > 1:
                flag = 1
                break
            else:
                count_arr[a//2] += 1
if flag == 1:
    print(0)
else:
    print(pow2(N//2))

Measured memory_bytes: 14008
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;

void main() {
  foreach (string line; stdin.lines) {
    int ans = 1;
    int n = line.chomp.to!int;

    for (int i = 1; i <= n; i++) {
      ans += i;
    }

    ans.writeln;
  }
}

Measured memory_bytes: 1044
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

H, W, K = mi()
C = [input() for i in range(H)]

B_i = 2 ** H
B_j = 2 ** W

ans = 0
for x in range(B_i):
    for y in range(B_j):
        cnt = 0
        for i in range(H):
            for j in range(W):
                if (x & (1 << i)) or y & (1 << j):
                    continue
                if C[i][j] == '#':
                    cnt += 1
        if cnt == K:
            ans += 1
                
print(ans)


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

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (300006)
ll n,m,mid;
bool ans;
string grid[16];
string cols[16];
vector<pi> v;
void solve(){
	vector<ll> rows;
	FOR(i,0,siz(v)-1) rows.eb(v[i].f);
	if(n&1) rows.eb(mid);
	DEC(i,siz(v)-1,0) rows.eb(v[i].s);
	FOR(i,0,m-1) cols[i].clear();
	FOR(i,0,m-1){
		for(auto j:rows) cols[i] += grid[j][i];
	}
	vector<bool> used(m-1, 0);
	bool mid_used = 0;
	FOR(i,0,m-1)if(!used[i]){
		reverse(all(cols[i]));
		ll match=-1;
		FOR(j,i+1,m-1)if(!used[j]){
			if(cols[i] == cols[j]) match=j;
		}
		if(match==-1 && (m&1) && !mid_used) {
			string tmp = cols[i];
			reverse(all(tmp));
			if(tmp != cols[i])return;
			mid_used = 1;
		}else if(match==-1) return;
		else {
			used[i]=used[match]=1;
		}
	}
	ans=1;
	return;
}
ll zero(ll bm){
	return __builtin_ctz(~bm);
}
void gen_pairs(ll bm){
	if(__builtin_popcount(bm) == n) {
		solve();
		return;
	}
	ll o = bm;
	ll f_zero = zero(bm);
	bm ^= 1<<f_zero;
	for(ll pos=zero(bm); __builtin_popcount(bm) != n; bm ^= 1<<pos, pos = zero(bm)){
		v.eb(f_zero, pos);
		gen_pairs(o^(1<<f_zero)^(1<<pos));
		v.pop_back();	
	}
}
int main(){
	FAST
	cin>>n>>m;
	FOR(i,0,n-1)cin>>grid[i];
	if(n&1) {
		FOR(i,0,n-1) mid=i, gen_pairs(1<<i);
	}else gen_pairs(0);
	cout<<(ans?"YES":"NO")<<'\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
  ll n;
  cin >> n;
  vector<ll> a(n),cp(n);
  ll p=0,sum=0;
  rep(i,n){
    cin >> a.at(i);
    cp.at(i)=abs(a.at(i));
    sum+=cp.at(i);
    if(a.at(i)<0){
      p++;
    }
  }
  if(p%2==1){
    ll mini=1e11;
    for(ll j=0;j<n;j++){
      mini=min(mini,cp.at(j));
    }
    sum=sum-2*mini;
  }
  cout << sum;
}
    
  
  

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

signed main(){
  int X,Y;
  cin>>X>>Y;
  string ans="No";
  int A[]={0,1,3,1,2,1,2,1,1,2,1,2,1};
  if(A[X]==A[Y])ans="Yes";
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#define ll long long
using namespace std;
int N,W;
int knapsack1( vector<ll>&wts,vector<ll>&val, vector<vector<ll>>&dp){
    //ll inc=0, exc=0;
    for(int i=0; i<=N; i++){
        for(int w=0; w<=W; w++){
            if( i==0||w==0  ) { dp[i][w]=0 ;}
            else{
             ll inc=0,exc=0;
             if( wts[i-1]<=w ){
                inc = val[i-1] + dp[i-1][w - wts[i-1]];
            }
                exc = dp[i-1][w];
                dp[i][w] = max(inc, exc);
            }
        }
    }
    return dp[N][W];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //int N,W;
    cin>>N>>W;
    vector<ll>wts(N);
    vector<ll>val(N);
    vector<vector<ll>>dp(N+1, vector<ll>(W+1, 0));
    for( int i=0; i<N; i++ ){
        cin>>wts[i]>>val[i];
    }
    ll ans = knapsack1(wts,val, dp);
   /* for(int i=0; i<=N; i++){
        for(int k=0;k<=W;k++){
            cout<<dp[i][k]<<"\t";
        }
        cout<<"\n";
    } */
    //cout<<ans;
    cout<<dp[N][W];

}


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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd


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

    int2(n, k);
    vector<int> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }

    //k = (k-1) % (n+1);
    k--;
    //std::cout << "k : " << k << std::endl;
    
    vi nxt(n);
    map<int, int> tmp;
    rep(i, n) {
        if (tmp.find(data[i]) != tmp.end()) {
            nxt[tmp[data[i]]] = i;
        }
        tmp[data[i]] = i;
    }
    rep(i, n) {
        if (tmp.find(data[i]) != tmp.end()) {
            nxt[tmp[data[i]]] = i;
        }
        tmp[data[i]] = i;
    }

    /*
    rep(i, n) {
        cout << nxt[i] << " ";
    }
    cout << endl;
    */

    //cout << "hop : ";
    int p = 0, hopcnt = 0;
    //while (k && p != n) {
    while (p != n) {
        //cout << p << " ";
        if (p < nxt[p]) {
            p = nxt[p];
        } else {
            //k--;
            hopcnt++;
            p = nxt[p];
        }
        //p = (p + 1) % n;
        p++;
    }
    //cout << p << endl;

    k = k % (hopcnt+1);
    p = 0;
    while (k) {
        if (p < nxt[p]) {
            p = nxt[p];
        } else {
            k--;
            p = nxt[p];
        }
        p++;
    }

    //if (!p) return 0;
    while (p < n) {
        if (p < nxt[p]) {
            p = nxt[p];
        } else {
            cout << data[p] << " ";
        }
        p++;
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 17152
import java.math.BigDecimal;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		BigDecimal total = BigDecimal.ZERO;

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

			String amountStr = sc.next();
			BigDecimal amount = new BigDecimal(amountStr);
			String unit = sc.next();

			if (unit.equals("JPY")) {
				total = total.add(amount);
			}
			if (unit.equals("BTC")) {
				total = total.add(amount.multiply(new BigDecimal(380000.0)));
			}

		}

		System.out.println(total);

	}

}


Measured memory_bytes: 23380
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <set>
#include <unordered_set>
#include <vector>
#include<valarray>
#include<map>

#include <utility>

#include <deque>
#include <queue>


using namespace std;
long long a[10001];
int main()
{
long long n;
cin>>n;
long long x,y,z;
long long counter;
set<long long >numbers;
for(int i=1;i<=n;i++)
{

    numbers.insert(i);
}


    for(x=1;x<=98;x++)
    {

        for (y = 1; y <= 98; y++)
        {
            for (z = 1; z <= 98; z++)
            {
                long long c=(x * x) + (y * y) + (z * z) + (x * y) + (z * x) + (z * y);

                auto it=numbers.find(c);
                if(it!=numbers.end())
                {
                    a[c]++;
                }
            }
        }

    }
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<endl;
    }



    return 0;
}

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

#define ll long long
#define ldb long double
#define rep(i, x, n, j) for(int i=x;i<(int)n;i+=j)
#define F first
#define S second
#define per(i, x, n, j) for(int i=(int)n-1;i>=0;i-=j)
#define all(v) v.begin(),v.end()
#define sz(a) (int)a.size()

const int N = 2000100;
const ll MOD = 1e9+7;
const ll inf = 1e18+5;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;

int _;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n; cin >> n;
	vector<pair<ll, ll>> v;
	rep(i,0,n,1){
		ll x, y; cin >> x >> y;
		v.push_back({x, y});
	}
	sort(all(v));
	vector<ll> v1, v2;
	for(auto &x: v){
		v1.push_back(x.F);
		v2.push_back(x.S);
	}
	sort(all(v1));
	sort(all(v2));

	if(n%2!=0){
		ll mid = n/2;
		cout << v2[mid]-v1[mid]+1;
		return 0;
	}

	else{
		ll m1 = n/2, m2 = (n/2)-1;
		ll d1 = v2[m1]-v1[m1]+1;
		ll d2 = v2[m2]-v1[m2]+1;
		cout << d1+d2-1 << endl;
		return 0;
	}
	return 0;
}


Measured memory_bytes: 11348
N = int(input())
s = [input() for _ in range(N)]
M = int(input())
t = [input() for _ in range(M)]
ans = 0
ex_list = []
for i in range(N):
    if s[i] not in ex_list:
        if s.count(s[i]) > t.count(s[i]):
            ans = max(s.count(s[i])-t.count(s[i]),ans)
            ex_list.append(s[i])
print(ans)

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

int main(){

    string s,t; cin >> s >> t;

    int n = s.size();

    for(int x=n-1;x>0;x--){
        int len = n-x;
        string fi = s.substr(0,x) , se = s.substr(x,len);
        
        string test = se + fi;
        if(test == t or s == t) {
            cout << "Yes\n";
            exit(0);
        }
        
    }
    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define in insert
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define mod 1000000007
#define sz(v) (int)(v.size())
#define all(x) x.begin(), x.end()
#define prec fixed << setprecision(20)
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define test int t; cin >> t; while(t--)

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef set<int> si;
typedef map<int, int> mii;
typedef vector<pii> vpi;

void solve() {
	int n;
	cin >> n;
	int sum = 0;
	rep(i, 1, n) {
		if (i % 3 != 0 && i % 5 != 0) {
			sum += i;
		}
	}
	cout << sum;
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	// test
	solve();

	return 0;
}

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

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

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

	int dist = y - x;

	map<int, int> ans;

	for (int i = 1; i <= n - 1; i++)
	{
		for (int j = 2; j <= n; j++)
		{			
			if (j <= x || y <= i)
			{
				ans[j - i]++;
			}
			else if (i <= x && y <= j)
			{
				ans[(j - i) - (dist - 1)]++;
			}
			else
			{
				int xdis = abs(x - i);
				int ydis = abs(y - j);

				int min_dis = min(j - i, xdis + 1 + ydis);

				ans[min_dis]++;
			}
		}
	}

	for (int k = 1; k < n; k++)
	{
		cout << ans[k] << endl;
	}
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
    public static void main(String [] args) {
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	int[] a = new int[n + 1];
    	int i = 1;
    	while(i <= n) {
    		a[i] = sc.nextInt();
    		i++;
    	}
    	int count = 0;
    	for (i = 1; i <= n; i++) {
    		int ai = a[i]; // 2
    		int aj = a[ai]; // 1
    		if (i == aj) {
    			count ++;
    		}
    		// 2 1 4 3
    		// 1 2 3 4
    		
    	}
    	System.out.println(count/2);
    }
}

Measured memory_bytes: 32300