akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#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 IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
/* const int MOD = 998244353; */
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


signed main() {
  int N, Q;
  cin >> N >> Q;

  vector<int> A(N), B(N);
  REP(i, N){
    A[i] = B[i] = N-1;
  }

  int ans = (N-2)*(N-2);

  int left = N-1;
  int up = N-1;
  REP(_, Q){
    int u, v;
    cin >> u >> v;
    v--;

    if(u == 1){
      if(v < left){
        for(int i = v; i < left; i++) B[i] = up;
        left = v;
      }
      ans -= B[v]-1;
    }else{
      if(v < up){
        for(int i = v; i < up; i++) A[i] = left;
        up = v;
      }
      ans -= A[v]-1;
    }
  }

  cout << ans << "\n";

  return 0;
}


Measured memory_bytes: 6252
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, K, D[10];
bool H[10];

bool hate(int V)
{
	while (V) {
		if (H[V % 10]) return false;
		V /= 10;
	}
	return true;
}
int main()
{
	scanf("%d%d", &N, &K);
	for (int i = 0; i < 10; ++i) H[i] = false;
	for (int i = 0; i < K; ++i) {
		scanf("%d", D + i);
		H[D[i]] = true;
	}
	for (;;) {
		if (hate(N)) {
			printf("%d\n", N);
			break;
		}
		++N;
	}
	return 0;
}

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

typedef long long LL;
const int MAXN = 3e6+5;
LL a[MAXN],b[MAXN], c[MAXN], d[MAXN], ans[MAXN];
bool cmp(LL A, LL B) {
    return A > B;
}
int main() {
    int A, B, C, K; cin>>A>>B>>C>>K;
    for(int i=0; i<A; i++) cin>>a[i];
    for(int i=0; i<B; i++) cin>>b[i];
    for(int i=0; i<C; i++) cin>>c[i];
    sort(a, a+A, cmp);
    sort(b, b+B, cmp);
    sort(c, c+C, cmp);
    int cnt = 0;
    for(int i=0; i<A; i++) for(int j=0; j<B; j++) d[cnt++] = a[i]+b[j];
    sort(d, d+cnt, cmp);
    int sum = 0;
    for(int i=0; i<min(K, cnt); i++) {
        for(int j=0; j<min(K, C); j++) {
            ans[sum++] = d[i]+c[j];
        }
    }
    sort(ans, ans+sum, cmp);
    for(int i=0; i<K; i++) cout<<ans[i]<<endl;
    return 0;
}


Measured memory_bytes: 39168
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int n,m,min,max,i;
  cin >> n >> m;
  int x[n],y[m];
  cin >> max >> min;
  for(i=0;i<n;i++){
    cin >> x[i];
    if(x[i]>max){
      max=x[i];
    }
  }
  for(i=0;i<m;i++){
    cin >> y[i];
    if(y[i]<min){
      min=y[i];
    }
  }
  if(max<min){
    cout << "No ";
  }
  cout << "War" << endl;
}

  


Measured memory_bytes: 256
while (line = gets) do

  hour = 60 * 60
  min = 60
  sec = 1

  times = line.split.map(&:to_i)

  start_time = times[0] * hour + times[1] * min + times[2] * sec
  end_time = times[3] * hour + times[4] * min + times[5] * sec

  working_time = end_time - start_time

  formatted_time = Array.new(3)

  formatted_time[0] = working_time / hour > 0 ? working_time / hour : 0
  formatted_time[1] = (working_time / min) % min > 0 ? (working_time / min) % min : 0
  formatted_time[2] = working_time % min

  puts "#{formatted_time[0]} #{formatted_time[1]} #{formatted_time[2]}"
end

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

int main() {
	char s;
	cin >> s;
	if (97 <= int(s)) {
		cout << "a" << endl;
	}
	else {
		cout << "A" << endl;
	}

	return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
typedef long long ll;
int A[3][3], N;
bool punched[3][3];
bool ok[3][3];
int a[3][3],n;

int main() {
string s;
cin >> s;
string t = s; 
reverse(s.begin(),s.end());
ll cnt=0;
rep(i,s.size()/2){
    if(s[i]!=t[i]){
        cnt++;
    }
}
cout << cnt << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long s=1e5+5;
long long n,a[s],b[s];
int main(){
   cin>>n;
   for (int i=1;i<=n+1;i++)
       scanf("%lld",&a[i]);
    for (int i=1;i<=n;i++)
       scanf("%lld",&b[i]);
    long long sum=0;
    for (int i=1;i<=n;i++)
        if (a[i]>=b[i]) 
           {
           	sum+=b[i];
           	a[i]-=b[i];
		   }
		else if ((a[i]+a[i+1])>=b[i])
		    {
		    	a[i+1]=a[i+1]+a[i]-b[i];
				a[i]=0;
		    	sum+=b[i];
			}
		else if (a[i]+a[i+1]<b[i])
		    {
		    	sum=sum+a[i]+a[i+1];
		    	a[i]=0;
		    	a[i+1]=0;
		    
			}
		cout<<sum<<endl;
   
   return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<utility>
#include<stack>
#include<queue>
#include<map>
#include<set>

using namespace std;

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)

#define PRINT(mpr) printf(#mpr "\n")
#define yOUT PRINT(Yes)
#define nOUT PRINT(No)
#define YOUT PRINT(YES)
#define NOUT PRINT(NO)
 
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

int main(){
    long long n, k;
    cin >> n >> k;
    long long ans = k*pow((k-1), n-1);
    cout << ans << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    string s;
    cin >> n >> s;
    ll ans = 0;
    int ncolor[256];
    for(int k = 0; k < n; k++) {
        int i_equal_k = 0;
        ncolor['R'] = 0;
        ncolor['G'] = 0;
        ncolor['B'] = 0;
        for(int j = 0; j < k; j++) {
            if(s[j] != s[k]) {
                int d = k - j;
                int i = j - d;
                ans += max(0, j - i_equal_k - ncolor[s[j]] - (i >= 0 and s[j] != s[i] and s[k] != s[i]));
            }
            i_equal_k += s[j] == s[k];
            ncolor[s[j]]++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3620
#include <algorithm>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

void A_Beginner(void) {

	int N, R;
	cin >> N >> R;
	cout << ((N >= 10) ? R : R + 100 * (10 - N));
	return;
}

void B_Digits(void) {

	int N, K;
	cin >> N >> K;

	for (int loop = 0; loop < 40; loop++) {
		if (N < (int)pow(K, loop)) {
			cout << loop << flush;
			return;
		}
	}
	return;
}

void C_Rally(void) {

	int N;
	cin >> N;

	vector<int> X(N);
	int min = 0, max = 0;
	for (int loop = 0; loop < N; loop++) {
		cin >> X[loop];
		if (loop == 0 || X[loop] < min) min = X[loop];
		if (loop == 0 || X[loop] > max) max = X[loop];
	}

	int p = 0;
	int req = 0;
	int reqMin = 0;
	for (p = min; p <= max; p++) {
		req = 0;
		for (int loop = 0; loop < N; loop++) {
			req += (X[loop] - p) * (X[loop] - p);
		}
		if (p == min || req < reqMin) reqMin = req;
	}

	cout << reqMin << flush;
	return;
}

int main(void) {

	//A_Beginner();
	//B_Digits();
	C_Rally();
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << x << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 1010


int dx6[2][7] = {{0,1,1,0,-1,-1},{0,1,1,0,-1,-1}};
int dy6[2][7] = {{1,1,0,-1,0,1},{1,0,-1,-1,-1,0}};


bool visited[6][201][201];
bool fur[SIZE][SIZE];

int main(){
  int sx,sy,gx,gy,lx,ly;
  int n;
  int fur_x[SIZE], fur_y[SIZE];
  
  scanf("%d%d%d%d%d",&sx,&sy,&gx,&gy,&n);

  for(int i=0;i<n;i++){
    scanf("%d%d",fur_x+i, fur_y+i);
    fur[fur_x[i]+100][fur_y[i]+100] = true;
  }

  scanf("%d%d",&lx,&ly);

  priority_queue<pair<pair<int,int>,pair<int,int> > > pq;
  // { {cost, turn} , {x, y} }

  pq.push({{0, 0},{sx,sy}});

  while(pq.size()){
    pair<pair<int,int>, pair<int,int> > p = pq.top();
    pq.pop();
    
    int cost = p.first.first;
    int turn = p.first.second;
    int x = p.second.first;
    int y = p.second.second;

    if(abs(x)>lx || abs(y)>ly) continue;
    if(fur[x+100][y+100]) continue;
    
    if(visited[turn][x+100][y+100]) continue;
    visited[turn][x+100][y+100] = true;

    if(x == gx && y == gy){
      printf("%d\n",-cost);
      return 0;
    }
    
    for(int i=0;i<6;i++){
      pq.push({{cost-(abs(x*y*turn)%6 != i), (turn+1)%6},{x+dx6[1-abs(x)%2][i],y+dy6[1-abs(x)%2][i]}});
    }
    pq.push({{cost-1, (turn+1)%6},{x,y}});
    
  }
  
  puts("-1");
  
  return 0;
}

Measured memory_bytes: 3952
#include<stdio.h>
int main() {
   int h, n;
   int a = 0;
   scanf("%d %d", &h, &n);
   int x[n];
   
   for(int i = 0; i < n; i++) {
      scanf("%d", &x[i]);
      a = a+x[i];
   }
   
   if(a >= h) {
      printf("Yes");
   }
   else {
      printf("No");
   }
   printf("\n");
   return 0;
}


Measured memory_bytes: 2068
#include <cstdio>
#include <iostream>
#include <cmath>

using namespace std;

#define MAXN 100010
#define INF 0x3f3f3f3f

int n;
int h[MAXN], f[MAXN];

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++ i)
		scanf("%d", &h[i]);
	f[1] = 0;
	f[2] = abs(h[2] - h[1]);
	for (int i = 3; i <= n; ++ i)
	{
		f[i] = INF;
		f[i] = min(f[i], min(f[i - 1] + abs(h[i] - h[i - 1]), f[i - 2] + abs(h[i] - h[i - 2])));
	}
	printf("%d", f[n]);
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ll long long int
#define vll vector<ll>
using namespace std;

int main(){
    string s;
    cin >> s;
    
    if(s == "AAA" or s == "BBB"){
        cout << "No" << endl;
    }
    
    else{
        cout << "Yes" << endl;
    }
    return 0;
}

Measured memory_bytes: 3636
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


//System.out.println();
public class Main implements Runnable { //クラス名はMain

    public static void main(String[] args) {
    	Thread.setDefaultUncaughtExceptionHandler((t,e)->System.exit(1));
        new Thread(null, new Main(), "", 16 * 1024 * 1024).start(); //16MBスタックを確保して実行
    }

    public void run() {
    	try {
	    	FastScannerMain1 sc = new FastScannerMain1(System.in);
	        int N = sc.nextInt();
	        int R = sc.nextInt();

	        if(N >=10) {
	        	System.out.println(R);
	        }else {
	        	int x=0;
	        	x = R + 100 * (10-N);
	        	System.out.println(x);
	        }

    	}catch(Exception e) {
    		e.printStackTrace();
    	}

    }
}


//高速なScanner
class FastScannerMain1 {
	private BufferedReader reader = null;
	private StringTokenizer tokenizer = null;

	public FastScannerMain1(InputStream in) {
		reader = new BufferedReader(new InputStreamReader(in));
		tokenizer = null;
	}

	public String next() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public String nextLine() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken("\n");
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nextLong();
		return a;
	}
}


Measured memory_bytes: 28500
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
int main() {
    int n;
    cin>>n;
    int i,j,k;
    double c[n],a[n+1][n+1];
    for(i=0;i<n;i++)
    cin>>c[i];
    memset(a,0.0,sizeof(a));
    a[0][0]=1;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=n;j++)
        {
            if(j==0)
            a[i][j]=a[i-1][j]*(1-c[i-1]);
            else
            a[i][j]=a[i-1][j]*(1-c[i-1])+a[i-1][j-1]*c[i-1];
        }
    }
    double ans=0.0;
    for(i=(n+1)/2;i<=n;i++)
    {
        ans+=a[n][i];
    }
    printf("%.10lf",ans);
	return 0;
}

Measured memory_bytes: 74116
#include <bits/stdc++.h>
#include <numeric>
#include <iterator>
#include <stdio.h>
#define ll long long
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define ff first
#define ss second
#define sz(a) int((a).size())
#define all(a) (a).begin(),(a).end()
#define fr(i,p,n) for(int i=p;i<n;i++)
#define precise cout << std::setprecision(10) << std::fixed;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
//ll M=1000000007;
//double pi=3.1415926535898;
ll M=  998244353;
typedef pair<int, int> pairs;
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}

int main()
{
    fastio; //precise;

    int T=1;
    //cin>>T;
    while(T--){
        int n,a,b,c;
        cin>>n;
        int h[n],dp[n][3];
        //multimap<int,int> m;
        fr(i,0,n){
            cin>>a>>b>>c;
            if(i==0) { dp[0][0]=a; dp[0][1]=b; dp[0][2]=c; }
            else {
                dp[i][0]=a+max(dp[i-1][1],dp[i-1][2]);
                dp[i][1]=b+max(dp[i-1][0],dp[i-1][2]);
                dp[i][2]=c+max(dp[i-1][1],dp[i-1][0]);
            }
        }
        a=max(max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);
        cout<<a<<endl;


    }
     return 0;
}
//cout<<"YES"<<endl;
//cout<<"NO"<<endl;


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

using namespace std ;

const int MAX = 1e5 + 10 ;

long long dist[MAX] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	int n , q;
	cin>>n>>q ;
	vector< vector< pair<long long , int> > >v(n+5) , v2(n+5);
	for(int i = 0 ; i < q ; ++i)
	{
		int x , y ;
		long long z ;
		cin>>x>>y>>z ;
		v[x].push_back({z , y}) ;
	}
	for(int i = 1 ; i <= n ; ++i)
		dist[i] = -1 ;
	dist[1] = 0 ;
	multiset< pair<long long , int> >s ;
	pair<long long , int>p ;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(s.size() > 0)
		{
			p = *s.begin() ;
			dist[i] = p.first ;
		}
		if(dist[i] == -1)
			return cout<<-1<<"\n" , 0 ;
		for(auto &j : v2[i])
			s.erase(s.find(j)) ;
		for(auto &j : v[i])
		{
			s.insert({j.first+dist[i] , j.second}) ;
			v2[j.second].push_back({j.first+dist[i] , j.second}) ;
		}
	}
	return cout<<dist[n]<<"\n" , 0 ;
}

Measured memory_bytes: 13440
def main():
    from fractions import gcd
    from functools import reduce
    def lcm(c,d):
        return c//gcd(c,d)*d
    mod=10**9+7
    n=int(input())
    a=[int(i) for i in input().split()]
    l=reduce(lcm,a)
    ans=sum(map(lambda x:l//x,a))
    print(ans%mod)
main()


Measured memory_bytes: 6100
use std::cmp;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();
    let a: Vec<usize> = sc.vec(n);
    let total = a.iter().sum::<usize>();

    let mut ans = std::usize::MAX;
    let mut sum = 0;
    for i in 0..n {
        sum += a[i];
        let first = (sum, i + 1);
        let second = (total - sum, n - (i + 1));
        let (first, second) = if first < second {
            (first, second)
        } else {
            (second, first)
        };

        if first.0 == second.0 {
            println!("0");
            return;
        }

        let reduce = second.0 - first.0;
        if first.0 >= second.1 {
            ans = cmp::min(ans, reduce);
        }
    }
    println!("{}", ans);
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write(&mut self, s: String) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 6396
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep3(i, l, n) for (int i = l; i < n; ++i)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define out(a) cout << a << endl
#define SZ(v) (int)v.size()
#define inf (int)(1e9+7)


int main() {
    int h, w;
    while (cin >> h >> w && h) {
        int dia = h * h + w * w;
        //out(dia);
        int tmp = inf;
        int a = 151, b = 151;
        int aa = 151, bb = 151;
        //制約大事よ
        rep3(i, 1, 150 + 1) {
            rep3(j, i + 1, 150 + 1) {
                int dia2 = i * i + j * j;
                if (dia2 > dia && dia2 < tmp) {
                    a = i; b = j; tmp = dia2;
                    //out(i << " " << j << " " << tmp);
                } else if (dia2 == dia && h < i && i < aa) {
                    a = i; b = j; tmp = dia2;
                    aa = i; bb = j;
                }
            }
        }
        out(a << " " << b);
    }
}



Measured memory_bytes: 3120
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <ctime>
using namespace std;
int n;
int prime[33333];
int c[111111],tot; 
int sum[111111];
void init() {
    for(int i=2;i<=1e5;i++)  
    {  
        if(!c[i])prime[tot++]=i;  
        for(int j=0;j<tot;j++)  
        {  
            if(i*prime[j]>1e5)break;  
            c[i*prime[j]]=true;  
            if(i%prime[j]==0)break;  
        }  
    }  
    for (int i = 3; i <= 100000; i ++ ) {
        sum [i] = sum[i - 1];

        if (i % 2 == 1 && !c[i] && !c[(i + 1) /2 ] ) sum[i]++;
    }
}
int gao(int l, int r) {
    return sum[r] - sum[l - 1];
}
int main() {
    init();
    cin >> n;
    int l, r;
    while (n--) {
        scanf("%d%d", &l, &r);
        int ans = gao(l,r);
        printf("%d\n", ans);
    }
	return 0;
}


Measured memory_bytes: 1408
using System.Collections.Generic;
using System.Linq;

public class Hello
{
    public static void Main()
    {
        hoge();
        //System.Console.ReadLine();
    }

    public static void hoge()
    {
        var line = System.Console.ReadLine();

        string[] hitachi = { "hi", "hihi", "hihihi", "hihihihi", "hihihihihi" };

        System.Console.WriteLine(hitachi.Contains(line) ? "Yes":"No") ;

    }
}



Measured memory_bytes: 13268
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define INF 50000
int main() {
	int N, M;
	cin >> N >> M;
	vector<int>C(M), T(N + 1, INF);
	for (int i = 0; i < M; i++) {
		cin >> C.at(i);
	}
	T.at(0) = 0;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j + C.at(i) <= N; j++) {
			T.at(j + C.at(i)) = min(T.at(j) + 1, T.at(j + C.at(i)));
		}
	}
	cout << T.at(N) << endl;
}


Measured memory_bytes: 3180
#include <bits/stdc++.h>
  
using namespace std;
  
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
  
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
  
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
  
int F()
{
    char ch;
    int x, a;
    while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
    if (ch == '-') ch = getchar(), a = -1;
    else a = 1;
    x = ch - '0';
    while (ch = getchar(), ch >= '0' && ch <= '9')
        x = (x << 1) + (x << 3) + ch - '0';
    return a * x;
}
  
const int N = 2010;
  
VI edge[N];
  
int n, k, dep[N], mxd;
  
void dfs(int u, int fa, int d)
{
    if (k & 1) if(d > k / 2 + 1) return;
    if (!(k & 1)) if (d > k / 2) return;
    ++dep[d];
    mxd = max(mxd, d);
    for (auto v : edge[u])
        if (v != fa)
        {
            dfs(v, u, d + 1);
        }
}
  
int main()
{
    gii(n, k);
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        gii(u, v);
        edge[u].pb(v);
        edge[v].pb(u);
    }
    int res = 0;
    for (int root = 1; root <= n; ++root)
    {
        int mx = 0, s = 1;
        for (auto son : edge[root])
        {
            mxd = 0;
            dfs(son, root, 1);
            if (k & 1) mx = max(mx, dep[k / 2 + 1]);
            if (k & 1) s -= dep[k / 2 + 1];
            for (int i = 1; i <= mxd; ++i) s += dep[i], dep[i] = 0;
        }
        res = max(res, s + mx);
    }
    printf("%d\n", n - res);
    return 0;
}

Measured memory_bytes: 384
N, K = parse.(Int, split(readline()))
hs = parse.(Int, split(readline()))

a = zeros(Int, N)
a[1] = 0
a[2] = abs(hs[2] - hs[1])

for i in 3:N
    #b = zeros(Int, K)
    #for j in 1:K
    #    b[j] = a[max(i-j,1)] + abs(hs[i] - hs[max(i-j,1)])
    #end
    b = a[max(i-K,1):i-1] .+ abs.(hs[i] .- hs[max(i-K,1):i-1])
    a[i] = minimum(b)
end
println(a[end])

Measured memory_bytes: 251336
s = list(input())
k = input()

if k == '1':
    print(s[0])
else:
    n = min(int(k), len(s))
    f = True
    for i in range(n):
        if s[i] != '1':
            print(s[i])
            f = False
            break
    if f:
        print(1)

Measured memory_bytes: 3060
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
col = []
row = []
rd = []
lu = []
board = [['.'] * 8 for _ in range(8)]

def put(r, c):
    global col, row, rd, lu, board
    col.append(c)
    row.append(r)
    rd.append(c-r)
    lu.append(r+c)
    board[r][c] = 'Q'

def canPut(i, j):
    if i not in row and j not in col and j-i not in rd and i+j not in lu:
        return True
    else:
        return False

def unput(i, j):
    global col, row, rd, lu, board
    col.remove(j)
    row.remove(i)
    rd.remove(j-i)
    lu.remove(i+j)
    board[i][j] = '.'

def rec(i):
    if i > 7:
        for p in range(8):
            print(''.join(board[p]))
        exit(0)
    # print("i: ", i)
    for j in range(8):
        if canPut(i, j):
            put(i, j)
            # print("put: ", i, j)
            k = i+1
            while k in row:
                k += 1
            rec(k)
            unput(i, j)

def main():
    global col, row, rd, lu
    n = int(input().strip())

    for i in range(n):
        r, c = list(map(int, input().strip().split()))
        put(r, c)
    k = 0
    while k in row:
        k += 1
    rec(k)


if __name__ == '__main__':
    main()



Measured memory_bytes: 5692
fn main() {
    let v = read_vec::<i32>();
    if v[0] == v[1] {
        println!("{}", v[2]);
    } else if v[1] == v[2] {
        println!("{}", v[0]);
    } else if v[0] == v[2] {
        println!("{}", v[1]);
    }
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

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

int ans = 0, n;

int main() {
  cin >> n;
  for(int i = 0; i < n; ++i) {
    int l, r;
    cin >> l >> r;
    ans += r - l + 1;
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
  INCANT;
  cin >> N;
  int a;
  rep(i, N) {
    cin >>a;
    a--;
    A[i]=a;
    Cnt[a]++; //0-index
  }
  ll sm = 0ll;
  rep(i,N) {
    sm+=Cnt[i]*(Cnt[i]-1)/2;
  }
  // ex. -6*5/2+5*4/2 = -5
  rep(i, N) {
    cout << sm - (Cnt[A[i]]-1) << "\n";
  }
  return 0;
}

Measured memory_bytes: 3968
import java.util.*;
public class Main {
	Scanner sc;
	
	String revStr(String str) {
		
		String ret = "";
		for(int j=str.length()-1;j>=0;j--) {
			ret += str.charAt(j);
		}
		return ret;
	}
	boolean rev1[] = {false,true,true,true};
	boolean rev2[] = {false,true,false,true};
	void run() {
		sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		for(int i=0;i<n;i++) {
			String str = sc.next();
			HashSet<String> strs = new HashSet<String>();
			for(int j=1;j<str.length();j++) {
				String sp1 = str.substring(0, j);
				String sp2 = str.substring(j);
				
				for(int k=0;k<4;k++) {
					if(rev1[k]) sp1 = revStr(sp1);
					if(rev2[k]) sp2 = revStr(sp2);
					strs.add(sp1.concat(sp2));
					strs.add(sp2.concat(sp1));
				}
			}
			System.out.println(strs.size());
		}
	}
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 16000
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>

using namespace std;

template <class T>
double area_of_polygon(vector<T> x, vector<T> y)
{
    assert(x.size() == y.size());
    int n = x.size();
    double ret = 0;
    for (int p = 0; p < n; p++) {
        for (int i = 1; i <= n - 2; i++) {
                int q = (p + i) % n, r = (p + i + 1) % n;
                T v1x, v1y, v2x, v2y;
                v1x = x[q] - x[p];
                v1y = y[q] - y[p];
                v2x = x[r] - x[p];
                v2y = y[r] - y[p];
                ret += v1x*v2y - v1y*v2x;
        }
    }
    ret = abs(ret / (2 * n));
    return ret;
}

int main(void)
{
    int num = 1;
    while (true) {
        int n;
        cin >> n;
        if (n == 0) {
            break;
        }
        vector<int> x(n), y(n);
        for (int i = 0; i < n; i++) {
            cin >> x[i] >> y[i];
        }
        printf("%d %.1lf\n", num++, area_of_polygon(x, y));
    }
    return 0;
}

Measured memory_bytes: 1236
from math import factorial
N,M = map(int,input().split())
n = factorial(N) % (10**9+7)
m = factorial(M) % (10**9+7)
if not (0 <= abs(N-M) <= 1) :
    ans = 0
elif N == M :
    ans = 2*n*m % (10**9+7)
else :
    ans = n*m % (10**9+7)
print(ans)


Measured memory_bytes: 4144
import java.util.Scanner;

class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        System.out.println(Math.min(k,n)*x+Math.max(0, n-k)*y);
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

int main(void){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  cout << max(a*b, c*d) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
void print() { cout << "\n"; }
template <class T> void print(const T &x) { cout << x << "\n"; }
template <class T, class... Args> void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
template <class T> void printVector(const vector<T> &v) {
    for(const T &x : v) {
        cout << x << " ";
    }
    cout << "\n";
}
using ll = long long;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
constexpr int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<vector<int>> dp(n + 1, vector<int>(5, INF));
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int k = 0; k < 5; k++) {
            for(int j = 0; j <= k; j++) {
                if(k == 0 || k == 4) {
                    chmin(dp[i][k], dp[i - 1][j] + a[i - 1]);
                } else if(k == 1 || k == 3) {
                    chmin(dp[i][k],
                          dp[i - 1][j] + (!a[i - 1] ? 2 : a[i - 1] & 1));
                } else {
                    chmin(dp[i][k], dp[i - 1][j] + !(a[i - 1] & 1));
                }
            }
        }
    }
    int ans = INF;
    for(int i = 0; i < 5; i++) {
        chmin(ans, dp[n][i]);
    }
    print(ans);
}

Measured memory_bytes: 12032
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1194&lang=jp

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	const int MAX = 60;
	const int HALF = MAX/2;
	
	while(true){
		long double res = 1e10;
		int _height[MAX+10] = {};
		int *height = _height + HALF + 5;
		int r, n;
		
		cin>>r>>n;
		
		if(!r && !n) break;
		
		for(int i = 0; i < n; i++){
			int xl, xr, h;
			
			cin>>xl>>xr>>h;
			
			for(int j = xl; j < xr; j++){
				height[j] = max(height[j], h);
			}
		}
		
		for(int j = -r; j < r; j++){
			long double dis1 = 0, dis2 = 0;
			
			dis1 = r - sqrt(r * r - j * j);
			dis2 = r - sqrt(r * r - (j + 1) * (j + 1));
			
			res = min(res, min(dis1, dis2) + height[j]);
		}
		
		cout<<res<<endl;
	}
	return 0;
}


Measured memory_bytes: 3296
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

bool f[10000] = {};

void _main() {
  int S;
  cin >> S;
  f[S] = true;

  int ans = 2;
  for (int t=S;; ans++) {
    if (t%2 == 0) t = t / 2;
    else          t = t * 3 + 1;
    if (f[t]) break;
    f[t] = true;
  }
  cout << ans << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n, k;
string s;
int main() {
    cin >> n >> k >> s;
    s.push_back('!');
    vector<int> R;
    vector<int> L;
    bool rlflg = true;
    bool rlfst = false;
    int cnt = 0;
    for(int i = 0; i <= n; ++i) {
        if(i == 0) {
            cnt++;
            if(s.at(i) == 'L') rlflg = false;
            else rlfst = true;
        }else {
            if(s.at(i) == 'L') {
                if(!rlflg) cnt++;
                else {
                    R.push_back(cnt);
                    rlflg = false;
                    cnt = 1;
                }
            }else if(s.at(i) == '!') {
                if(rlflg) R.push_back(cnt);
                else L.push_back(cnt);
            }else {
                if(rlflg) cnt++;
                else {
                    L.push_back(cnt);
                    rlflg = true;
                    cnt = 1;
                }
            }
        }
    }

    int sum = 0;
    for(int i = 0; i < R.size(); ++i) {
        sum += R.at(i)-1;
    }
    for(int i = 0; i < L.size(); ++i) {
        sum += L.at(i)-1;
    }

    int Llen = L.size();
    int Rlen = R.size();

    if(rlfst) {
        if(k < Llen) {
            for(int i = 0; i < k; ++i) sum += 2;
        }else {
            if(Llen == Rlen) {
                for(int i = 0; i < Llen-1; ++i) sum += 2;
                sum += 1;
            }else {
                for(int i = 0; i < Llen; ++i) sum += 2;
            }
        }
    }else {
        if(k < Rlen) {
            for(int i = 0; i < k; ++i) sum += 2;
        }else {
            if(Llen == Rlen) {
                for(int i = 0; i < Rlen-1; ++i) sum += 2;
                sum += 1;
            }else {
                for(int i = 0; i < Rlen; ++i) sum += 2;
            }
        }
    }

    cout << sum << endl;
}

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

int main() {
	int N, L, R;
	while (cin >> N >> L >> R) {
		if (N == 0) return 0;
		vector<int> A(N);
		for (int i = 0; i < N; i++) cin >> A[i];
		A.push_back(1), N++;
		int ANS = 0;
		for (int i = L; i <= R; i++) {
			for (int j = 0; j < N; j++) {
				if (i % A[j] == 0) {
					if (j % 2 == 0) ANS++;
					break;
				}
			}
		}
		cout << ANS << endl;
	}
}


Measured memory_bytes: 3056
<?php
fscanf(STDIN, "%d", $n);
$list = explode(" ", trim(fgets(STDIN)));
$ans = 1;
sort($list);
foreach($list as $value){

    $ans *= $value;
    if($ans >= 1000000000000000001){
        echo -1;
        exit;
    }
}
echo $ans;

Measured memory_bytes: 25488
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int Mire = 196470;

int main(){
  int n;
  cin >> n;
  while(n--){
    int y, m, d;
    cin >> y >> m >> d;

    if(y % 3 == 0) d += (m-1) * 20;
    else{
      for(int i = m-1 ; i >= 1 ; i--){
	if(i % 2 == 1) d += 20;
	else d += 19;
      }
    } 
    for(int i = y-1 ; i >= 1 ; i--){
      if(i % 3 == 0) d += 200;
      else d += 195;
    }
    cout << Mire - d + 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 0
// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define error(args...) 
#endif

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}

int main(){
    iostream_init();
    int N;
    while(cin >> N) {
        int L = 3*N;
        vector<LL> A(L);
        REP(i, L) cin >> A[i];

        vector<LL> first_sum(L+1, -1);
        vector<LL> second_sum(L+1, -1);
        {
            multiset<LL> s;
            for(int i = 0; i < A.size(); i++) {
                if(s.size() < N) {
                    s.insert(A[i]);
                    if(s.size() == N) {
                        first_sum[i+1] = 0;
                        for(LL x : s) { first_sum[i+1] += x; }
                    }
                } else if(*s.begin() < A[i]) {
                    LL add = A[i] - *s.begin();
                    s.erase(s.begin());
                    s.insert(A[i]);
                    first_sum[i+1] = first_sum[i] + add;
                } else {
                    first_sum[i+1] = first_sum[i];
                }
            }
        }
        {
            multiset<LL> s;
            for(int i = A.size()-1; i >= 0; i--) {
                if(s.size() < N) {
                    s.insert(-A[i]);
                    if(s.size() == N) {
                        second_sum[i] = 0;
                        for(LL x : s) { second_sum[i] += -x; }
                    }
                } else if(-(*s.begin()) > A[i]) {
                    LL add = A[i] - (-*s.begin());
                    s.erase(s.begin());
                    s.insert(-A[i]);
                    second_sum[i] = second_sum[i+1] + add;
                } else {
                    second_sum[i] = second_sum[i+1];
                }
            }
        }
        LL ans = LLONG_MIN;
        for(int i = 0; i < A.size(); i++) {
            if(first_sum[i+1] != -1 && second_sum[i+1] != -1) {
                ans = max(ans, first_sum[i+1] - second_sum[i+1]);
            }
        }
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 12032
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define LL long long
#define fgx cerr<<"--------------"<<endl;
#define dgx cerr<<"=============="<<endl;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
const int MAXN = 100010;
const int INF = 2147483600;

int N,D1,D2;
bool Vis[710][710];

inline void solve(int P){
	int K=0; while(P%4==0) P>>=2,K++;
	if(P%4==3) return ;
	if(P%4==1) {
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				Vis[i][j]&=((((i>>K)^(j>>K))&1)^1);
	} else{
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++) 
				Vis[i][j]&=(((i>>K)&1)^1);
	} return ;
}

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	N=read(),D1=read(),D2=read();
	int cnt=N*N;
	N<<=1; memset(Vis,1,sizeof(Vis));
	solve(D1); solve(D2); 
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(Vis[i][j]){
				printf("%d %d\n",i,j); --cnt;
				if(!cnt) return 0;
			}
		}
	}
	return 0;
}




Measured memory_bytes: 4260
#include <bits/stdc++.h>
using namespace std;
#define int long long

typedef pair<int, int> Pi;
#define fi first
#define se second

map <int, int> dp[105];

main()
{
  int N, W;
  int w, v;
  map<int, int>::iterator it;
  
  cin >> N >> W;
  
  dp[0][0] = 0;
  for(int i = 0; i < N; i++) {
    cin >> w >> v;
    for(it = dp[i].begin(); it != dp[i].end(); it++) {
      int dw = (it -> fi), nw = dw + w;

      if(dp[i + 1].find(dw) == dp[i + 1].end()) {
	dp[i + 1][dw] = dp[i][dw];
      } else {
	dp[i + 1][dw] = max(dp[i][dw], dp[i + 1][dw]);
      }

      if(nw > W) continue;
      if(dp[i + 1].find(nw) == dp[i + 1].end()) {
	dp[i + 1][nw] = dp[i][dw] + v;
      } else {
	dp[i + 1][nw] = max(dp[i + 1][nw], dp[i][dw] + v);
      }
      
    }

  }
  
  int maxv = 0;
  for(it = dp[N].begin(); it != dp[N].end(); it++) {
    maxv = max(maxv, it -> se);
  }

  cout << maxv << endl;

  return 0;
}


Measured memory_bytes: 6400
/*https://atcoder.jp/contests/dp/tasks/dp_d*/
#include <iostream>
#include <vector>
using namespace std;
int max(int a, int b){
	return a > b ? a : b;
}
int main(){
	int n, W;
	cin >> n >> W;
	vector<long long>w(n), v(n);
	for (int i = 0; i < n; i++)
		cin >> w[i] >> v[i];
	vector<long long> dp(W + 1, 0);
	for (int i = 0; i < n; i++){
		for (int j = W - w[i]; j >= 0; j--){
			dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i]);
		}
	}
	cout << dp[W];
}

Measured memory_bytes: 1024
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

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

    map<string,Int> Dict;

    Int ans = 0;
    for(int i = 0;i < N;i++) {
        string s;
        cin>>s;
        
        vector<char> M;
        for(int j = 0;j < 10;j++) {
            M.push_back(s[j]);
        }
        sort(M.begin(),M.end());
        string temp = "";
        for(auto v:M)
            temp += v;

        if(Dict[temp] > 0) {
            ans += Dict[temp];
        }
        Dict[temp]++;
    }

    cout<<ans<<endl;

    return 0;
}



Measured memory_bytes: 12800
import scala.io.{StdIn => in}

object Main extends App {
  val n = in.readInt
  val h = in.readLine.split(" ").map(_.toInt)

  var cnt = 0
  var max = 0
  for(i <- 0 until n) {
    if(h(i) >= max) {
      cnt += 1
    }
    max = h(i) max max
  }

  val ans = cnt
  println(ans)
}

Measured memory_bytes: 25396
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), i##_max = (b); i < i##_max; ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()

using namespace std;
using vi = vector<int>;
using i64 = int64_t;

constexpr int INF = 1 << 30;
constexpr int MOD = 1000000007;

template <typename T>
void print(vector<T> v) {
  REP(i, v.size()) {
    if (i) cout << " ";
    cout << v[i];
  }
  cout << endl;
}

// 二重連鎖木
// 左子右兄弟表現
struct Node { int p, l, r; };

void print(vector<Node> &T, vi &D, int u) {
  cout << "node " << u << ": ";
  cout << "parent = " << T[u].p << ", ";
  cout << "depth = " << D[u] << ", ";
  
  if (T[u].p == -1) cout << "root, ";
  else if (T[u].l == -1) cout << "leaf, ";
  else cout << "internal node, ";
  
  cout << "[";
  for (int i = 0, c = T[u].l; c != -1; ++i, c = T[c].r) {
    if (i) cout << ", ";
    cout << c;
  }
  cout << "]" << endl;
}

void rec(vector<Node> &T, vi &D, int u, int p) {
  D[u] = p;
  if (T[u].r != -1) rec(T, D, T[u].r, p);
  if (T[u].l != -1) rec(T, D, T[u].l, p+1);
}

int main() {
  int n, l;
  cin >> n;
  vector<Node> T(n);
  vi D(n);
  REP(i, n) T[i].p = T[i].l = T[i].r = -1;
  REP(i, n) {
    int id, k;
    cin >> id >> k;
    REP(j, k) {
      int c;
      cin >> c;
      if (j == 0) T[id].l = c;
      else T[l].r = c;
      l = c;
      T[c].p = id;
    }
  }
  int r;
  REP(i, n) {
    if (T[i].p == -1) r = i;
  }
  rec(T, D, r, 0);
  REP(i, n) print(T, D, i);
}


Measured memory_bytes: 9040
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define min(a, b) ((a) < (b))?(a):(b)

#define INF 1001001001

struct list {
	int item;
	struct list * next;
} *to[100005];

void initializeList(int n)
{
	int i;
	for (i = 0; i < n; i++) {
		to[i] = NULL;
	}
}

struct list *insertList(int i, int x)
{
	struct list *p;
	if (to[i] == NULL) {
		to[i] = (struct list *)malloc(sizeof(struct list));
		to[i]->item = x;
		to[i]->next = NULL;
	} else {
		p = to[i];
		to[i] = (struct list *)malloc(sizeof(struct list));
		to[i]->item = x;
		to[i]->next = p;
	}

	return to[i];
}

struct queue {
	int item;
	struct queue *next;
} *head, *tail;

void initialize_queue(void)
{
	head = tail = (struct queue *)malloc(sizeof(struct queue));
}

void addqueue(int x)
{
	tail->item = x;
	tail->next = (struct queue *)malloc(sizeof(struct queue));
	tail = tail->next;
}

int removequeue(void)
{
	int x;
	struct queue *p;
	p = head;
	head = p->next;
	x = p->item;
	free(p);
	return x;
}

int main()
{
	int ret, i, n, m;
	int a, b;
	int *prev;
	int *dist;
	int v, u;
	struct list *pu;
	
	int ans;
	ret = scanf("%d %d", &n, &m);

	initializeList(n);
	prev = (int *) malloc(sizeof(int)*n);
	for (i = 0; i < n; i++)
		prev[i] = -1;
	dist = (int *) malloc(sizeof(int)*n);
	for (i = 0; i < n; i++)
		dist[i] = INF;
	
	for (i = 0; i < m; i++) {
		ret = scanf(" %d %d", &a, &b);
		--a;
		--b;
		to[a] = insertList(a, b);
		to[b] = insertList(b, a);
	}

	initialize_queue();
	dist[0] = 0;
	addqueue(0);
	do {
		v = removequeue();
		for (pu = to[v]; pu != NULL; pu = pu->next) {
			u = pu->item;
			if (dist[u] !=INF) continue;
			dist[u] = dist[v]+1;
			prev[u] = v;
			addqueue(u);
		}
	} while(head != tail);
	
	printf("Yes\n");
	for (i = 0; i < n; i++) {
		if (i == 0) continue;
		ans = prev[i];
		++ans;
		printf("%d\n", ans);
	}
	
	fflush(stdout);
	free(prev);
	free(dist);
	return EXIT_SUCCESS;
}


Measured memory_bytes: 18576
#include <bits/stdc++.h>
typedef long long ll;
#define MP make_pair
#define PB push_back
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;
int main(){
	int m,n;
	char s[9];
	while(scanf("%d%d",&m,&n)&&m&&n){
		bool mem[m];
		REP(i,m)mem[i]=false;
		int p=0,c=1;
		for(int i=1;i<=n;i++){
			scanf("%s",s);
			if(c<m){
				int f=0;
				if(i%15==0){
					if(strcmp(s,"FizzBuzz"))f=1;
				}else if(i%5==0){
					if(strcmp(s,"Buzz"))f=1;
				}else if(i%3==0){
					if(strcmp(s,"Fizz"))f=1;
				}else{
					if(i!=atoi(s))f=1;
				}
				if(f)mem[p]=i,++c;
				do{
					p=(p+1)%m;
				}while(mem[p]);
			}
		}
		int f=0;
		for(int i=0;i<m;i++){
			if(!mem[i]){
				printf(f?" %d":"%d",i+1);
				f=1;
			}
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 1196
#include<iostream>
#include<string.h>
#include<vector>
#include<list>
#include<stdio.h>
#include<math.h>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << "debug " << x << endl;
using namespace std;

int main(){
    int distance[10], v1, v2;
    char garbage;
    while(cin >> distance[0]){
        cin >> garbage;
        double lineLength = distance[0];
        range(i,1,10){
            cin >> distance[i] >> garbage;
            lineLength+= distance[i];
        }
        cin >> v1 >> garbage >> v2;
        double sum_v = v1 + v2;
        double time = lineLength / sum_v;
        double pass_location = v1 * time;
        rep(i,10){
            pass_location-= static_cast<double>(distance[i]);
            if(pass_location <= 0){
                cout << i + 1 << endl;
                break;
            }
        }
    }
}

Measured memory_bytes: 1160