Poj Solution 3115

http://poj.org/problem?id=3115

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

int main( ) {
    __int64 m[4][2], *ans = m[0], *temp = m[1], *id = m[2], *idt = m[3], s1, s2, 
        mem[2][20], *res = mem[0], *rest = mem[1];
    int en[20], ti[20];
    int f, p, e, a, i, j;

    while( 1 ) {
        scanf( "%d%d%d%d", &f, &p, &e, &a );
        e *= a;
        if( f == 0 && p == 0 && e == 0 && a == 0 ) break;

        ans[0] = 0;
        ans[1] = 50000000000;
        id[0] = 0;
        id[1] = 1;

        for( j=0; j<f; j++ )
            res[j] = 50000000000;

        for( i=0; i<p; i++ ) {
            for( j=0; j<f; j++ ) {
                scanf( "%d%d", en+j, ti+j );
                en[j] *= ti[j];
            }

            temp[0] = 50000000000;
            temp[1] = 50000000000;

            for( j=0; j<f; j++ ) {
                s1 = ans[0] + en[j] + e*(j!=id[0]);
                s2 = ans[1] + en[j] + e*(j!=id[1]);
                rest[j] = res[j] + en[j];

                if( s1 < rest[j] ) rest[j] = s1;
                if( s2 < rest[j] ) rest[j] = s2;

                if( rest[j] < temp[0] ) {
                    temp[1] = temp[0], idt[1] = idt[0];
                    temp[0] = rest[j], idt[0] = j;
                }
                else if( rest[j] < temp[1] )
                    temp[1] = rest[j], idt[1] = j;
            }

            swap( temp, ans );
            swap( id, idt );
            swap( rest, res );
        }

        printf( "%I64dn", ans[0] );
    }
    return 0;
}


											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *